Stream processing with ordered types Joseph Cutler

Format:

Book

Thesis/Dissertation

Author/Creator:

Cutler, Joseph, author.

Contributor:

University of Pennsylvania. Computer and Information Science., degree granting institution.

Language:

English

Subjects (All):

Computer science.

Computer engineering.

0984.

0464.

0800.

Local Subjects:

Computer science.

Computer engineering.

0984.

0464.

0800.

Genre:

Academic theses

Physical Description:

1 online resource (191 pages)

Contained In:

Dissertations Abstracts International 87-12B

Place of Publication:

Ann Arbor : ProQuest Dissertations and Theses, 2026

Language Note:

English

Summary:

Stream processing is ubiquitous in modern computing, from distributed data analytics to digital signal processing and AI inference. Stream programs must process data incrementally in order of arrival, while also operating in bounded memory, since inputs are unbounded. Despite its ubiquity, programming models for stream processing remain relatively impoverished compared to general-purpose programming.Common stream programming languages and libraries restrict programmers to a fixed set of stream-processing combinators like map, filter, or folded When a task does not cleanly decompose into a composition of combinators, programmers must drop all the way down to writing streaming state machines manually. Meanwhile, functional programmers enjoy the same combinators for lists, but have a much more pleasant alternative for when combinators don't do the trick: pattern matching and general recursion.In this dissertation, we build the best of both worlds with the help of ordered types, a lesser-used kind of substructural type system. With ordered types, programmers must use variables in order. By aligning the variable usage ordering with the streaming data arrival ordering, we can give streaming semantics to general recursive functional list programs.We present two language designs exploring this idea. The first, Delta, uses a bunched ordered type system to guarantee incremental (but not bounded-space) processing. Delta programs execute as state machines that consume input prefixes and produce output prefixes on demand. The type system supports novel stream types including concatenation (a sequential composition of streams) and parallel streams. We investigate the metatheory of Delta and prove that programs are deterministic regardless of the arrival order of parallel data.The second language, Yoink, uses a different ordered type system to give streaming semantics, this time guaranteeing bounded space usage. Yoink accomplishes this by adopting a pull-based semantics, where programs explicitly request input rather than reacting to pushed data. Last, we build a compiler for Yoink that produces fused imperative programs

Notes:

Source: Dissertations Abstracts International, Volume: 87-12, Section: B.

Advisors: Pierce, Benjamin C. Committee members: Zdancewic, Stephan A.; Weirich, Stephanie C.; Tannen, Val; Xie, Ningning

Ph.D. University of Pennsylvania 2026

Vendor supplied data

Local Notes:

School code: 0175

ISBN:

9798247980698

Access Restriction:

Restricted for use by site license