Search a title or topic

Over 20 million podcasts, powered by 

Player FM logo
Artwork

Content provided by Aaron Stump. All podcast content including episodes, graphics, and podcast descriptions are uploaded and provided directly by Aaron Stump or their podcast platform partner. If you believe someone is using your copyrighted work without your permission, you can follow the process outlined here https://podcastplayer.com/legal.
Player FM - Podcast App
Go offline with the Player FM app!

Schematic Affine Recursion, Oh My!

18:49
 
Share
 

Manage episode 501832197 series 2823367
Content provided by Aaron Stump. All podcast content including episodes, graphics, and podcast descriptions are uploaded and provided directly by Aaron Stump or their podcast platform partner. If you believe someone is using your copyrighted work without your permission, you can follow the process outlined here https://podcastplayer.com/legal.

To solve the problem raised in the last episode, I propose schematic affine recursion. We saw that affine lambda calculus (where lambda-bound variables are used at most once) plus structural recursion does not enforce termination, even if you restrict the recursor so that the function to be iterated is closed when you reduce ("closed at reduction"). You have to restrict it so that recursion terms are disallowed entirely unless the function to be iterated is closed ("closed at construction"). But this prevents higher-order functions like map, which need to repeat a computation involving a variable f to be mapped over the elements of a list. The solution is to allow schematic definition of terms, using schema variables ranging over closed terms.

  continue reading

178 episodes

Artwork
iconShare
 
Manage episode 501832197 series 2823367
Content provided by Aaron Stump. All podcast content including episodes, graphics, and podcast descriptions are uploaded and provided directly by Aaron Stump or their podcast platform partner. If you believe someone is using your copyrighted work without your permission, you can follow the process outlined here https://podcastplayer.com/legal.

To solve the problem raised in the last episode, I propose schematic affine recursion. We saw that affine lambda calculus (where lambda-bound variables are used at most once) plus structural recursion does not enforce termination, even if you restrict the recursor so that the function to be iterated is closed when you reduce ("closed at reduction"). You have to restrict it so that recursion terms are disallowed entirely unless the function to be iterated is closed ("closed at construction"). But this prevents higher-order functions like map, which need to repeat a computation involving a variable f to be mapped over the elements of a list. The solution is to allow schematic definition of terms, using schema variables ranging over closed terms.

  continue reading

178 episodes

All episodes

×
 
Loading …

Welcome to Player FM!

Player FM is scanning the web for high-quality podcasts for you to enjoy right now. It's the best podcast app and works on Android, iPhone, and the web. Signup to sync subscriptions across devices.

 

Copyright 2025 | Privacy Policy | Terms of Service | | Copyright
Listen to this show while you explore
Play