Well-founded Recursion over Contextual Objects
We present a core programming language that supports writing well-founded structurally recurs-ive functions using simultaneous pattern matching on contextual LF objects and contexts. The main technical tool is a coverage checking algorithm that also generates valid recursive calls. To establish cons...
Main Authors: | , |
---|---|
Other Authors: | |
Format: | Text |
Language: | English |
Subjects: | |
Online Access: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.673.2963 http://www.cs.mcgill.ca/%7Ebpientka/papers/wfrec-dep.pdf |
id |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.673.2963 |
---|---|
record_format |
openpolar |
spelling |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.673.2963 2023-05-15T15:41:40+02:00 Well-founded Recursion over Contextual Objects Brigitte Pientka Andreas Abel The Pennsylvania State University CiteSeerX Archives application/pdf http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.673.2963 http://www.cs.mcgill.ca/%7Ebpientka/papers/wfrec-dep.pdf en eng http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.673.2963 http://www.cs.mcgill.ca/%7Ebpientka/papers/wfrec-dep.pdf Metadata may be used without restrictions as long as the oai identifier remains attached to it. http://www.cs.mcgill.ca/%7Ebpientka/papers/wfrec-dep.pdf Dependent Types Logical Frameworks Digital Object Identifier 10.4230/LIPIcs.xxx.yyy.p text ftciteseerx 2016-01-08T17:28:31Z We present a core programming language that supports writing well-founded structurally recurs-ive functions using simultaneous pattern matching on contextual LF objects and contexts. The main technical tool is a coverage checking algorithm that also generates valid recursive calls. To establish consistency, we define a call-by-value small-step semantics and prove that every well-typed program terminates using a reducibility semantics. Based on the presented methodo-logy we have implemented a totality checker as part of the programming and proof environment Beluga where it can be used to establish that a total Beluga program corresponds to a proof. Text Beluga Beluga* Unknown |
institution |
Open Polar |
collection |
Unknown |
op_collection_id |
ftciteseerx |
language |
English |
topic |
Dependent Types Logical Frameworks Digital Object Identifier 10.4230/LIPIcs.xxx.yyy.p |
spellingShingle |
Dependent Types Logical Frameworks Digital Object Identifier 10.4230/LIPIcs.xxx.yyy.p Brigitte Pientka Andreas Abel Well-founded Recursion over Contextual Objects |
topic_facet |
Dependent Types Logical Frameworks Digital Object Identifier 10.4230/LIPIcs.xxx.yyy.p |
description |
We present a core programming language that supports writing well-founded structurally recurs-ive functions using simultaneous pattern matching on contextual LF objects and contexts. The main technical tool is a coverage checking algorithm that also generates valid recursive calls. To establish consistency, we define a call-by-value small-step semantics and prove that every well-typed program terminates using a reducibility semantics. Based on the presented methodo-logy we have implemented a totality checker as part of the programming and proof environment Beluga where it can be used to establish that a total Beluga program corresponds to a proof. |
author2 |
The Pennsylvania State University CiteSeerX Archives |
format |
Text |
author |
Brigitte Pientka Andreas Abel |
author_facet |
Brigitte Pientka Andreas Abel |
author_sort |
Brigitte Pientka |
title |
Well-founded Recursion over Contextual Objects |
title_short |
Well-founded Recursion over Contextual Objects |
title_full |
Well-founded Recursion over Contextual Objects |
title_fullStr |
Well-founded Recursion over Contextual Objects |
title_full_unstemmed |
Well-founded Recursion over Contextual Objects |
title_sort |
well-founded recursion over contextual objects |
url |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.673.2963 http://www.cs.mcgill.ca/%7Ebpientka/papers/wfrec-dep.pdf |
genre |
Beluga Beluga* |
genre_facet |
Beluga Beluga* |
op_source |
http://www.cs.mcgill.ca/%7Ebpientka/papers/wfrec-dep.pdf |
op_relation |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.673.2963 http://www.cs.mcgill.ca/%7Ebpientka/papers/wfrec-dep.pdf |
op_rights |
Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
_version_ |
1766374553033900032 |