From Haskell to a New Structured Combinator Processor

Yukang Xie; Craig Ramsay; Robert James Stewart; Hans-Wolfgang Loidl

doi:10.1007/978-3-031-99751-8_7

From Haskell to a New Structured Combinator Processor

Yukang Xie
, Craig Ramsay
, Robert James Stewart
, Hans-Wolfgang Loidl

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

522 Downloads (Pure)

Abstract

This paper presents KappaMutor, a new graph reduction processor, along with its Haskell compiler. KappaMutor is based on structured combinators, a recently proposed combinator encoding, which is more flexible and efficient than fine-grained SKI combinators. The processor exploits parallel memories to enable single-cycle reduction of structured combinators while maintaining good compactness, utilising less than 1% of the logical resources on a modern FPGA. Its Haskell compiler implements novel code generation strategies designed to minimise combinator usage and achieve full laziness --- the first such implementation for structured combinators, to the best of our knowledge. Based on our measurements, structured combinators can reduce runtimes by 9% to 58%, compared to running equivalent SKI combinator programs on KappaMutor.

Original language	English
Title of host publication	Trends in Functional Programming
Subtitle of host publication	26th International Symposium, TFP 2025, Oxford, UK, January 14–16, 2025, Revised Selected Papers
Publisher	Springer
Pages	139-164
Number of pages	26
ISBN (Electronic)	9783031997518
ISBN (Print)	9783031997501
DOIs	https://doi.org/10.1007/978-3-031-99751-8_7
Publication status	Published - 1 Nov 2025
Event	26th International Symposium on Trends in Functional Programming 2025 - University of Oxford, Oxford, United Kingdom Duration: 13 Jan 2025 → 16 Jan 2025 Conference number: 26 https://trendsfp.github.io/2025/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	15652
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	26th International Symposium on Trends in Functional Programming 2025
Abbreviated title	TFP 2025
Country/Territory	United Kingdom
City	Oxford
Period	13/01/25 → 16/01/25
Internet address	https://trendsfp.github.io/2025/

Keywords

Graph reduction
Structured combinators
Hardware design
Haskell

Access to Document

10.1007/978-3-031-99751-8_7

Cite this

@inproceedings{abcc9e8c8893420aaad019b51cc14124,

title = "From Haskell to a New Structured Combinator Processor",

abstract = "This paper presents KappaMutor, a new graph reduction processor, along with its Haskell compiler. KappaMutor is based on structured combinators, a recently proposed combinator encoding, which is more flexible and efficient than fine-grained SKI combinators. The processor exploits parallel memories to enable single-cycle reduction of structured combinators while maintaining good compactness, utilising less than 1\% of the logical resources on a modern FPGA. Its Haskell compiler implements novel code generation strategies designed to minimise combinator usage and achieve full laziness --- the first such implementation for structured combinators, to the best of our knowledge. Based on our measurements, structured combinators can reduce runtimes by 9\% to 58\%, compared to running equivalent SKI combinator programs on KappaMutor.",

keywords = "Graph reduction, Structured combinators, Hardware design, Haskell",

author = "Yukang Xie and Craig Ramsay and Stewart, \{Robert James\} and Hans-Wolfgang Loidl",

year = "2025",

month = nov,

day = "1",

doi = "10.1007/978-3-031-99751-8\_7",

language = "English",

isbn = "9783031997501",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "139--164",

booktitle = "Trends in Functional Programming",

note = "26th International Symposium on Trends in Functional Programming 2025, TFP 2025 ; Conference date: 13-01-2025 Through 16-01-2025",

url = "https://trendsfp.github.io/2025/",

}

Xie, Y, Ramsay, C, Stewart, RJ & Loidl, H-W 2025, From Haskell to a New Structured Combinator Processor. in Trends in Functional Programming: 26th International Symposium, TFP 2025, Oxford, UK, January 14–16, 2025, Revised Selected Papers. Lecture Notes in Computer Science, vol. 15652, Springer, pp. 139-164, 26th International Symposium on Trends in Functional Programming 2025, Oxford, United Kingdom, 13/01/25. https://doi.org/10.1007/978-3-031-99751-8_7

From Haskell to a New Structured Combinator Processor. / Xie, Yukang; Ramsay, Craig; Stewart, Robert James et al.
Trends in Functional Programming: 26th International Symposium, TFP 2025, Oxford, UK, January 14–16, 2025, Revised Selected Papers. Springer, 2025. p. 139-164 (Lecture Notes in Computer Science; Vol. 15652).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - From Haskell to a New Structured Combinator Processor

AU - Xie, Yukang

AU - Ramsay, Craig

AU - Stewart, Robert James

AU - Loidl, Hans-Wolfgang

N1 - Conference code: 26

PY - 2025/11/1

Y1 - 2025/11/1

N2 - This paper presents KappaMutor, a new graph reduction processor, along with its Haskell compiler. KappaMutor is based on structured combinators, a recently proposed combinator encoding, which is more flexible and efficient than fine-grained SKI combinators. The processor exploits parallel memories to enable single-cycle reduction of structured combinators while maintaining good compactness, utilising less than 1% of the logical resources on a modern FPGA. Its Haskell compiler implements novel code generation strategies designed to minimise combinator usage and achieve full laziness --- the first such implementation for structured combinators, to the best of our knowledge. Based on our measurements, structured combinators can reduce runtimes by 9% to 58%, compared to running equivalent SKI combinator programs on KappaMutor.

AB - This paper presents KappaMutor, a new graph reduction processor, along with its Haskell compiler. KappaMutor is based on structured combinators, a recently proposed combinator encoding, which is more flexible and efficient than fine-grained SKI combinators. The processor exploits parallel memories to enable single-cycle reduction of structured combinators while maintaining good compactness, utilising less than 1% of the logical resources on a modern FPGA. Its Haskell compiler implements novel code generation strategies designed to minimise combinator usage and achieve full laziness --- the first such implementation for structured combinators, to the best of our knowledge. Based on our measurements, structured combinators can reduce runtimes by 9% to 58%, compared to running equivalent SKI combinator programs on KappaMutor.

KW - Graph reduction

KW - Structured combinators

KW - Hardware design

KW - Haskell

UR - https://www.scopus.com/pages/publications/105019313918

U2 - 10.1007/978-3-031-99751-8_7

DO - 10.1007/978-3-031-99751-8_7

M3 - Conference contribution

SN - 9783031997501

T3 - Lecture Notes in Computer Science

SP - 139

EP - 164

BT - Trends in Functional Programming

PB - Springer

T2 - 26th International Symposium on Trends in Functional Programming 2025

Y2 - 13 January 2025 through 16 January 2025

ER -

From Haskell to a New Structured Combinator Processor

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Embargoed Document

Fingerprint

Dataset and source code for TFP 2025 paper: "From Haskell to a New Structured Combinator Processor"

Cite this

From Haskell to a New Structured Combinator Processor

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Embargoed Document

Fingerprint

Datasets

Dataset and source code for TFP 2025 paper: "From Haskell to a New Structured Combinator Processor"

Cite this