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