390:
231:
65:. However, since Milner's model was essentially based on the syntax of PCF it was considered less than satisfactory. The first two fully abstract models not employing syntax were formulated during the 1990s. These models are based on
385:{\displaystyle {\frac {\Gamma \;\vdash \;t\;:{\textbf {nat}},\quad \quad \Gamma \;\vdash \;s_{0}\;:\sigma ,\quad \quad \Gamma \;\vdash \;s_{1}\;:\sigma }{\Gamma \;\vdash \;{\textbf {if}}(t,s_{0},s_{1})\;:\sigma }}}
673:
787:
749:
477:
843:
77:
demonstrated that no effectively presentable fully abstract model could exist, since the question of program equivalence in the finitary fragment of PCF is not decidable.
1115:
134:
is a type, such that no variable name is duplicated. One then defines typing judgments of terms-in-context in the usual way for the following syntactical constructs:
594:
559:
1296:
520:
1306:
1301:
1221:
1017:
1316:
1281:
73:. For a time it was felt that neither of these models was completely satisfactory, since they were not effectively presentable. However,
1260:
604:
51:
1311:
398:
s will be interpreted as booleans here with a convention like zero denoting truth, and any other number denoting falsity)
756:
678:
973:
891:"PCF is a programming language for computable functions, based on LCF, Scott’s logic of computable functions."
429:
70:
1001:
47:
183:
31:
1050:
870:
This model is not fully abstract for PCF; but it is fully abstract for the language obtained by adding a
1109:
43:
1018:"Correspondence between Operational and Denotational Semantics: The Full Abstraction Problem for PCF"
792:
74:
1025:
1256:
861:
1244:
1230:
1175:
1142:
1095:
1062:
996:
988:
949:
851:
523:
176:
20:
564:
529:
934:
484:
930:
66:
58:
35:
1248:
1180:
1163:
1083:
1290:
1235:
1216:
992:
954:
421:
969:
62:
1198:
1276:
872:
28:
1212:
1194:
39:
479:(the natural numbers with a bottom element adjoined, with the flat ordering)
1147:
1100:
1067:
1130:
850:
Lambda abstraction and application are interpreted by making use of the
46:
or a simplified version of modern typed functional languages such as
412:
A relatively straightforward semantics for the language is the
668:{\displaystyle x_{1}:\sigma _{1},\;\dots ,\;x_{n}:\sigma _{n}}
854:
structure of the category of domains and continuous functions
1024:. Oxford University Press. pp. 269–356. Archived from
1082:
Abramsky, S., Jagadeesan, R., and
Malacaria, P. (2000).
1020:. In Abramsky, S.; Gabbay, D.; Maibau, T. S. E. (eds.).
42:. It can be considered to be an extended version of the
795:
759:
681:
607:
567:
532:
487:
432:
234:
1217:"A type-theoretic alternative to CUCH, ISWIM, OWHY"
1199:"A type-theoretic alternative to CUCH, ISWIM, OWHY"
38:in 1977, based on previous unpublished material by
837:
781:
743:
667:
588:
553:
514:
471:
384:
1002:20.500.11820/731c88c6-cdb1-4ea0-945e-f39d85de11f1
831:
821:
809:
799:
737:
720:
702:
685:
581:
571:
546:
536:
508:
491:
450:
436:
782:{\displaystyle \Gamma \;\vdash \;x\;:\;\sigma }
925:
923:
744:{\displaystyle \!]\times \;\dots \;\times \!]}
1049:Hyland, J. M. E. & Ong, C.-H. L. (2000).
1044:
1042:
905:Programming language for Computable Functions
847:Variable terms are interpreted as projections
187:fixed point combinator (making terms of type
8:
1114:: CS1 maint: multiple names: authors list (
1129:O'Hearn, P. W. & Riecke, J. G (1995).
974:"Fully abstract models of typed λ-calculi"
935:"LCF considered as a programming language"
817:
813:
775:
771:
767:
763:
713:
709:
641:
634:
372:
329:
325:
313:
302:
298:
283:
272:
268:
249:
245:
241:
1234:
1179:
1146:
1099:
1066:
1000:
953:
794:
758:
728:
693:
680:
659:
646:
625:
612:
606:
585:
566:
550:
531:
504:
486:
472:{\displaystyle \!]:=\mathbb {N} _{\bot }}
463:
459:
458:
441:
440:
431:
363:
350:
331:
330:
307:
277:
254:
253:
235:
233:
896:
789:are interpreted as continuous functions
1282:Lexer and Parser for PCF written in SML
919:
884:
1107:
1297:Programming languages created in 1977
1253:Foundations for Programming Languages
1022:Handbook of Logic in Computer Science
901:Programming with Computable Functions
7:
442:
332:
255:
1131:"Kripke Logical Relations and PCF"
803:
760:
464:
322:
295:
265:
238:
89:of PCF are inductively defined as
14:
1307:Educational programming languages
420:Types are interpreted as certain
61:model for PCF was first given by
893:Programming Computable Functions
522:is interpreted as the domain of
25:Programming Computable Functions
1164:"Finitary PCF is not decidable"
294:
293:
264:
263:
161:Application (of a term of type
1302:Academic programming languages
838:{\displaystyle \!]\;\to \;\!]}
832:
828:
822:
818:
814:
810:
806:
800:
796:
738:
734:
721:
717:
703:
699:
686:
682:
675:is interpreted as the product
596:, with the pointwise ordering.
582:
578:
572:
568:
547:
543:
537:
533:
509:
505:
498:
492:
488:
451:
447:
437:
433:
369:
337:
1:
1181:10.1016/S0304-3975(00)00194-8
1051:"On Full Abstraction for PCF"
899:). It is also referred to as
860:is interpreted by taking the
1236:10.1016/0304-3975(93)90095-b
1222:Theoretical Computer Science
1168:Theoretical Computer Science
993:10.1016/0304-3975(77)90053-6
981:Theoretical Computer Science
955:10.1016/0304-3975(77)90044-5
942:Theoretical Computer Science
1317:Programming language theory
1135:Information and Computation
1088:Information and Computation
1055:Information and Computation
16:A typed functional language
1333:
1084:"Full Abstraction for PCF"
71:Kripke logical relations
1277:Introduction to RealPCF
130:is a variable name and
1206:Unpublished Manuscript
1148:10.1006/inco.1995.1103
1101:10.1006/inco.2000.2930
1068:10.1006/inco.2000.2917
1016:Ong, C.-H. L. (1995).
839:
783:
745:
669:
590:
555:
516:
473:
408:Denotational semantics
386:
840:
784:
746:
670:
591:
589:{\displaystyle \!]\,}
556:
554:{\displaystyle \!]\,}
517:
474:
387:
224:with the typing rule:
191:out of terms of type
142:is part of a context
44:typed lambda calculus
1312:Functional languages
793:
757:
679:
605:
565:
530:
485:
430:
232:
1162:Loader, R. (2001).
515:{\displaystyle \!]}
206:) and predecessor (
122:is a list of pairs
32:functional language
1249:"The Language PCF"
931:Plotkin, Gordon D.
835:
779:
741:
665:
586:
551:
512:
469:
382:
169:to a term of type
107:, there is a type
1245:Mitchell, John C.
876:operator to PCF.
862:least fixed point
753:Terms in context
444:
416:. In this model,
380:
334:
257:
214:and the constant
1324:
1266:
1240:
1238:
1209:
1203:
1186:
1185:
1183:
1174:(1–2): 341–364.
1159:
1153:
1152:
1150:
1126:
1120:
1119:
1113:
1105:
1103:
1079:
1073:
1072:
1070:
1046:
1037:
1036:
1034:
1033:
1013:
1007:
1006:
1004:
978:
966:
960:
959:
957:
939:
927:
908:
889:
852:cartesian closed
844:
842:
841:
836:
788:
786:
785:
780:
750:
748:
747:
742:
733:
732:
698:
697:
674:
672:
671:
666:
664:
663:
651:
650:
630:
629:
617:
616:
595:
593:
592:
587:
560:
558:
557:
552:
524:Scott-continuous
521:
519:
518:
513:
478:
476:
475:
470:
468:
467:
462:
446:
445:
391:
389:
388:
383:
381:
379:
368:
367:
355:
354:
336:
335:
320:
312:
311:
282:
281:
259:
258:
236:
220:The conditional
210:) operations on
21:computer science
1332:
1331:
1327:
1326:
1325:
1323:
1322:
1321:
1287:
1286:
1273:
1263:
1243:
1211:
1201:
1193:
1190:
1189:
1161:
1160:
1156:
1128:
1127:
1123:
1106:
1081:
1080:
1076:
1048:
1047:
1040:
1031:
1029:
1015:
1014:
1010:
976:
968:
967:
963:
937:
929:
928:
921:
916:
911:
890:
886:
882:
864:of the argument
791:
790:
755:
754:
724:
689:
677:
676:
655:
642:
621:
608:
603:
602:
563:
562:
528:
527:
526:functions from
483:
482:
457:
428:
427:
410:
405:
359:
346:
321:
303:
273:
237:
230:
229:
202:The successor (
83:
17:
12:
11:
5:
1330:
1328:
1320:
1319:
1314:
1309:
1304:
1299:
1289:
1288:
1285:
1284:
1279:
1272:
1271:External links
1269:
1268:
1267:
1261:
1241:
1213:Scott, Dana S.
1195:Scott, Dana S.
1188:
1187:
1154:
1141:(1): 107–116.
1121:
1094:(2): 409–470.
1074:
1061:(2): 285–408.
1038:
1008:
961:
948:(3): 223–255.
918:
917:
915:
912:
910:
909:
883:
881:
878:
868:
867:
866:
865:
855:
848:
834:
830:
827:
824:
820:
816:
812:
808:
805:
802:
798:
778:
774:
770:
766:
762:
751:
740:
736:
731:
727:
723:
719:
716:
712:
708:
705:
701:
696:
692:
688:
684:
662:
658:
654:
649:
645:
640:
637:
633:
628:
624:
620:
615:
611:
599:
598:
597:
584:
580:
577:
574:
570:
549:
545:
542:
539:
535:
511:
507:
503:
500:
497:
494:
490:
480:
466:
461:
456:
453:
449:
439:
435:
409:
406:
404:
401:
400:
399:
392:
378:
375:
371:
366:
362:
358:
353:
349:
345:
342:
339:
328:
324:
319:
316:
310:
306:
301:
297:
292:
289:
286:
280:
276:
271:
267:
262:
252:
248:
244:
240:
226:
225:
218:
200:
179:
174:
159:
138:Variables (if
116:
115:
97:
82:
79:
67:game semantics
59:fully abstract
36:Gordon Plotkin
34:introduced by
15:
13:
10:
9:
6:
4:
3:
2:
1329:
1318:
1315:
1313:
1310:
1308:
1305:
1303:
1300:
1298:
1295:
1294:
1292:
1283:
1280:
1278:
1275:
1274:
1270:
1264:
1262:9780262133210
1258:
1254:
1250:
1246:
1242:
1237:
1232:
1228:
1224:
1223:
1218:
1214:
1207:
1200:
1196:
1192:
1191:
1182:
1177:
1173:
1169:
1165:
1158:
1155:
1149:
1144:
1140:
1136:
1132:
1125:
1122:
1117:
1111:
1102:
1097:
1093:
1089:
1085:
1078:
1075:
1069:
1064:
1060:
1056:
1052:
1045:
1043:
1039:
1028:on 2006-01-07
1027:
1023:
1019:
1012:
1009:
1003:
998:
994:
990:
986:
982:
975:
971:
970:Milner, Robin
965:
962:
956:
951:
947:
943:
936:
932:
926:
924:
920:
913:
906:
902:
898:
897:Mitchell 1996
894:
888:
885:
879:
877:
875:
874:
863:
859:
856:
853:
849:
846:
845:
825:
776:
772:
768:
764:
752:
729:
725:
714:
710:
706:
694:
690:
660:
656:
652:
647:
643:
638:
635:
631:
626:
622:
618:
613:
609:
600:
575:
540:
525:
501:
495:
481:
454:
426:
425:
423:
419:
418:
417:
415:
407:
402:
397:
393:
376:
373:
364:
360:
356:
351:
347:
343:
340:
326:
317:
314:
308:
304:
299:
290:
287:
284:
278:
274:
269:
260:
250:
246:
242:
228:
227:
223:
219:
217:
213:
209:
205:
201:
198:
194:
190:
186:
185:
180:
178:
177:λ-abstraction
175:
172:
168:
164:
160:
157:
153:
149:
145:
141:
137:
136:
135:
133:
129:
125:
121:
114:
110:
106:
102:
98:
95:
92:
91:
90:
88:
80:
78:
76:
72:
68:
64:
60:
55:
53:
49:
45:
41:
37:
33:
30:
26:
22:
1252:
1226:
1220:
1210:Appeared as
1205:
1171:
1167:
1157:
1138:
1134:
1124:
1110:cite journal
1091:
1087:
1077:
1058:
1054:
1030:. Retrieved
1026:the original
1021:
1011:
984:
980:
964:
945:
941:
904:
900:
895:is used by (
892:
887:
871:
869:
857:
413:
411:
395:
221:
215:
211:
207:
203:
196:
192:
188:
182:
170:
166:
162:
155:
151:
147:
143:
139:
131:
127:
123:
119:
117:
112:
108:
104:
100:
93:
86:
84:
75:Ralph Loader
63:Robin Milner
56:
24:
18:
1229:: 411–440.
873:parallel or
414:Scott model
27:(PCF) is a
1291:Categories
1032:2006-01-19
914:References
601:A context
140:x : σ
124:x : σ
99:For types
40:Dana Scott
826:σ
815:→
804:Γ
777:σ
765:⊢
761:Γ
726:σ
715:×
711:…
707:×
691:σ
657:σ
636:…
623:σ
576:τ
541:σ
502:τ
499:→
496:σ
465:⊥
403:Semantics
377:σ
327:⊢
323:Γ
318:σ
300:⊢
296:Γ
288:σ
270:⊢
266:Γ
243:⊢
239:Γ
96:is a type
1247:(1996).
1215:(1993).
1197:(1969).
987:: 1–22.
972:(1977).
933:(1977).
154: :
126:, where
422:domains
146:, then
120:context
52:Haskell
1259:
81:Syntax
1202:(PDF)
977:(PDF)
938:(PDF)
880:Notes
87:types
29:typed
1257:ISBN
1116:link
208:pred
204:succ
181:The
103:and
85:The
69:and
1231:doi
1227:121
1176:doi
1172:266
1143:doi
1139:120
1096:doi
1092:163
1063:doi
1059:163
997:hdl
989:doi
950:doi
903:or
561:to
443:nat
396:nat
256:nat
212:nat
94:nat
50:or
19:In
1293::
1255:.
1251:.
1225:.
1219:.
1204:.
1170:.
1166:.
1137:.
1133:.
1112:}}
1108:{{
1090:.
1086:.
1057:.
1053:.
1041:^
995:.
983:.
979:.
944:.
940:.
922:^
455::=
424:.
333:if
222:if
195:→
165:→
150:⊢
118:A
111:→
57:A
54:.
48:ML
23:,
1265:.
1239:.
1233::
1208:.
1184:.
1178::
1151:.
1145::
1118:)
1104:.
1098::
1071:.
1065::
1035:.
1005:.
999::
991::
985:4
958:.
952::
946:5
907:.
858:Y
833:]
829:]
823:[
819:[
811:]
807:]
801:[
797:[
773::
769:x
739:]
735:]
730:n
722:[
718:[
704:]
700:]
695:1
687:[
683:[
661:n
653::
648:n
644:x
639:,
632:,
627:1
619::
614:1
610:x
583:]
579:]
573:[
569:[
548:]
544:]
538:[
534:[
510:]
506:]
493:[
489:[
460:N
452:]
448:]
438:[
434:[
394:(
374::
370:)
365:1
361:s
357:,
352:0
348:s
344:,
341:t
338:(
315::
309:1
305:s
291:,
285::
279:0
275:s
261:,
251::
247:t
216:0
199:)
197:σ
193:σ
189:σ
184:Y
173:)
171:σ
167:τ
163:σ
158:)
156:σ
152:x
148:Γ
144:Γ
132:σ
128:x
113:τ
109:σ
105:τ
101:σ
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.