Step-Indexed Normalization for a Language with General Recursion

Details Step-Indexed Normalization for a Language with General Recursion Step-Indexed Normalization for a Language with General Recursion

2012-02-14

arxiv.org/abs/1202.2918v1

EPTCS 76, 2012, pp. 25-39

Computer Science

Programming Languages

In Proceedings MSFP 2012, arXiv:1202.2407

Scientific paper

10.4204/EPTCS.76.4

The Trellys project has produced several designs for practical dependently typed languages. These languages are broken into two fragments-a_logical_fragment where every term normalizes and which is consistent when interpreted as a logic, and a_programmatic_fragment with general recursion and other convenient but unsound features. In this paper, we present a small example language in this style. Our design allows the programmer to explicitly mention and pass information between the two fragments. We show that this feature substantially complicates the metatheory and present a new technique, combining the traditional Girard-Tait method with step-indexed logical relations, which we use to show normalization for the logical fragment.

Affiliated with

Also associated with

No associations

Rating

Step-Indexed Normalization for a Language with General Recursion does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Step-Indexed Normalization for a Language with General Recursion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Step-Indexed Normalization for a Language with General Recursion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-88568