-
Notifications
You must be signed in to change notification settings - Fork 5
/
eoomi2024.scrbl
2026 lines (1769 loc) · 107 KB
/
eoomi2024.scrbl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
#lang scribble/lncs
@; -*- Scribble -*-
@title{The Essence of Object-Orientation: @linebreak[]
Modularity and Incrementality, @linebreak[]
or: @linebreak[]
Lambda, the Ultimate Object}
@abstract{
We argue that the essence of Object-Orientation (OO)
is a mechanism for reified (in-language) Incremental Modularity:
we do it by first making a semi-formal problem statement,
then identifying the simplest solution from first principles,
thereby reconstructing the basic concepts of OO on top of the pure λ-calculus.
We discuss how various features of OO languages
can facilitate or hinder this Incremental Modularity,
from forms of inheritance, to classes themselves, to mutation.
Our exploration yields answers that sometimes coincide with
prevalent academic discourse or industrial practice,
but sometimes goes against one or both.
}
@authors[
@author{François-René Rideau}
]
@institutes[
@institute{@emph{Mutual Knowledge Systems, Inc.}@linebreak[]
@email|{fare@mukn.com}|}
]
@(require scriblib/bibtex
(only-in scribble/core make-paragraph make-style)
(only-in scribble/manual racket racketblock code codeblock litchar itemize item)
(only-in scribble/example examples make-base-eval)
(only-in scriblib/footnote note)
(only-in scribble-abbrevs appendix)
(only-in scribble-math/dollar $)
syntax/parse/define
"util/examples-module.rkt"
"util/enumitem.rkt"
"util/util.rkt"
(for-label racket))
@(define-simple-macro (c a ...) (elem #:style 'tt a ...))
@(define-simple-macro (Code a ...) (verbatim a ...))
@(define-simple-macro (r a ...) (racket a ...))
@(define-simple-macro (Definitions a ...) (examples/module poof #:no-result a ...))
@(define-simple-macro (Examples a ...) (examples #:eval poof #:no-result a ...))
@(define-simple-macro (Checks a ...) (examples #:eval poof #:label #f a ...))
@(define-simple-macro (λ formals body ...) (lambda formals body ...))
@(define-simple-macro (TODO body ...) '())
@(declare-examples/module poof racket
(provide (all-defined-out))
(require syntax/parse/define))
@examples/module[poof #:hidden
(define (Y f) ;; fixed-point operator
(define (self x) (f self x))
self)
]
@(define (principle . x) (bold (emph x)))
@(define-bibtex-cite "poof.bib" ~cite citet generate-bibliography)
@section{The Essence of OO}
@subsection{OO in 2 lines of FP}
Our previous paper@~cite{poof2021} @; “Prototypes: Object-Orientation, Functionally”
reconstructs Object-Orientation (OO) on top of a kernel of two simple functions
(see @seclink{simplest_prototypes}).
These functions slightly generalize a decades-old theoretical-only model @;@~cite{bracha1990mixin},
except one that had twenty-five years later been made the actual practical implementation
of systems managing software at a very large scale (see @seclink{minimal_design_maximal_outreach}).
@subsection{OO as Incremental Modularity}
We herein develop an idea that was only briefly mentioned in the previous paper:
@principle{OO is a mechanism to specify computations in modular increments}.
We thus reconstruct from first principles a functional design of basic OO concepts,
each of them justified by how it is a necessary affordance toward this purpose.
Our design mostly reprises well known ideas,
though with a few original enhancements or clarifications
(such as the notion of conflation).
We explain how our modern presentation choice of design elements,
compare early designs
and how modularity justifies using multiple inheritance over mixin inheritance,
or conflating prototypes and instances (or classes and types) rather than keep them separate.
In this present paper, we will elaborate on this relationship
between OO and Incremental Modularity.
Without presenting a complete theory of Modularity (sketched in @citet{ngnghm9})
we introduce some semi-formal criteria for what Modularity and Incrementality mean.
We can then make our previous claims about OO and Modularity more explicit and less informal.
@TODO{cite inheritance1996 for incrementality, something else for modularity}
@subsection{Claims}
The present paper claim the following original contributions:
@TODO{see defsection in poof.scrbl, use that here and everywhere.}
@itemize[
@;#:style enumparenalph
@item{Dispel common misconceptions as to what OO is about (@seclink{what_oo_is_not_about}).}
@item{Propose criteria for Modularity (@seclink{modularity})
and Incrementality (@seclink{incrementality})
in terms of information needed to make software modifications.}
@item{Elucidate how Incrementality and Modularity go together (@seclink{incremental_modularity}).}
@item{Map the basic concepts of OO to modularity and incrementality
(@seclink{internal_incremental_modularity}),
as embodied in the simplest kind of OO Prototypes
using mixin inheritance (@seclink{simplest_prototypes}).}
@item{Explain how single inheritance
is less expressive and modular than mixin inheritance (@seclink{single_inheritance}),
that is less so than multiple inheritance (@seclink{multiple_inheritance}).}
@item{Show how “structs” with the performance benefits of single-inheritance
can be expressed in a system with multiple-inheritance
(@seclink{single_and_multiple_inheritance_together}).}
@item{Discuss how purity and laziness make OO more modular,
and solve difficult initialization order issues (@seclink{laziness}).}
@; ^ and are actually used in practice in most OO languages—but only at the metalevel.
@item{Discuss how purity and laziness make OO more modular,
and solve difficult initialization order issues (@seclink{laziness}).}
@; ^ and are actually used in practice in most OO languages—but only at the metalevel.
@item{Expose the conflation between prototypes and instances (or classes and types)
at the heart of most OO, and why it contributes to modularity (@seclink{objects}).}
@item{Clarify the relationship between Prototype OO and Class OO,
and why Prototypes, being first-class, enable more modularity (@seclink{classes}).}
@item{Generalize OO methods from fixed slots to functional lenses,
very simply enable modular features like method combinations (@seclink{optics}).}
@item{Show how the “typeclass” approach can be more composable and thus
more modular than the “class” approach (@seclink{typeclasses}).}
@item{Provide a pure functional modular solution to issues with
multiple dispatch vs single dispatch, friend classes or mutually recursive classes,
by making library namespace management an explicit part of the language
(@seclink{global}).}]
Many of the concepts and relationships we tackle have long been part of OO practice and lore,
yet have been largely neglected in scientific literature and formalization attempts.
@subsection[#:tag "what_oo_is_not_about"]{What OO is @emph{not} about}
We make the bold claim that the essence of OO is Incremental Modularity.
Yet, many other slogans or concepts have been claimed to be essential to OO in the past.
We can summarily dismiss those claims as follows:
@subsubsection[#:tag "not_about_classes"]{Classes}
Many think that classes, as introduced by Simula 67@~cite{Simula1968}
(though implementing a concept previously named by Hoare@~cite{hoare1965record}),
are essential to OO, and only ever care to implement, use, formalize,
study, teach or propagandize class-based OO (a.k.a. Class OO).
Yet the existence since 1976@~cite{Kahn1976 Borning1977 Kahn1979 Borning1979 Borning1981 Rees82t:a adams88oopscheme}
of languages using class-less prototype-based OO
(a.k.a. Prototype OO)@~cite{Lieberman1986 Borning1986 chambers1989efficient Lawall89SelfInScheme},
and the fact that the single most used OO language in the world, JavaScript@~cite{TopPL2022},
uses prototypes@~cite{EcmaScript:15}, provide clear counter-evidence to this belief.
The original inventors of OO also later unified classes, prototypes and procedures
into a general notion of “patterns”@~cite{kristensen1987beta},
which also voids any appeal to their authority in declaring classes as such as essential to OO.
Of course, classes are an @emph{important} concept in OO.
The situation is similar to that of types in FP,
in which they are an important though not essential concept,
as evidenced by the historical preexistence and continued use of the untyped λ-calculus
and the wide adoption of dynamically typed functional languages like Scheme or Nix.
Actually, we’ll demonstrate below in @seclink{classes} @;TODO FIX REF
how classes are a indeed special case of prototypes, and
how they precisely relate to types.
@subsubsection{Imperative Programming}
Many people assume that OO requires that
all slots of all objects should be mutable, or be so by default,
and that OO requires mutation deep in its object initialization protocols.
Furthermore, they assume the same eager evaluation model
for function calls and variable definitions as in every common imperative language.
@TODO{CITE? C++ Perl5 Python Java JavaScript Scala Ruby Go (see GitHub)}
Meanwhile, many have of late claimed that purity (the lack of side-effects including mutable state)
is essential to FP, making it incompatible with OO.
Some purists even argue that normal-order evaluation (call-by-name or call-by-need)
is also essential for true FP,
making it even more incompatible with OO.
Now there are many good historical reasons,
having to do with speed and memory limitations at runtime as well as compile-time
for which the first OO languages, as well as most languages until recently,
were using state and side-effects everywhere, and an eager evaluation model, at least by default.
Yet with early 1980s slogans like “objects are a poor man’s closures” and
“closures are a poor man’s objects”@~cite{adams88oopscheme},
the problem back then was clearly not whether OO could be done purely with functions,
but whether it made practical sense to program purely with functions in general.
That question that would only be slowly answered positively, in theory in the early 1990s
and in practice in the mid 2000s to mid 2010s, as Haskell grew up to become a practical language.
@; darcs 2003, cabal 2005, bytestring 2005, “cabal hell” 2006, ghc6 2006, pandoc 2006, xmonad 2007, “Real World Haskell” 2008. Stack 2015 “made non-trivial haskell programs & scripts repeatable”
@; There’s obviously a lot of subjectivity there—but I expect an S curve such that whichever arbitrary threshhold criteria you choose the answer would be at about the same time.
Yet, there are (a) pure models of OO such as those of
Kamin, Reddy, Cook and Bracha@~cite{Kamin1988 ObjectsAsClosures Cook1989 bracha1990mixin},
(b) pure lazy dynamic OO languages such as Jsonnet or Nix@~cite{jsonnet dolstra2008nixos},
and pure OO systems such as presented in this paper and its predecessors@~cite{poof2021}
@; TODO maybe mention foreshadowing by Oleg Kiselyov ?
and (c) languages happily combining OO and FP such as Common Lisp or Scala
@;TODO cite ScalaZ, etc.
with plenty of libraries restricting themselves to pure functional objects only.
These provide ample evidence that OO does not at all require mutation,
but can be done in a pure setting, and is very compatible with FP, purity,
and even with laziness and normal-order evaluation.
We could even argue that Haskell typeclasses embody OO@~cite{typeclasses LIL2012},
though its designers might not wholly embrace the OO tradition. @TODO{CITE}
@subsubsection{Inheritance as opposed to Composition}
@;TODO: the terms have a specific meaning within OO, @~cite{}
Some argue that the essence of OO is to choose a side in a conflict
between Inheritance and Composition, wherein one has to model every possible domain
in terms of inheritance, especially so where it can be preferred compared
to alternatives not involving it,
and even more so when such alternative involves FP and composition.
But OO and FP are just distinct concepts neither of which subsumes the other,
that thus fit distinct sets of situations.
@;Each distinct concept has its set of situations that it fits,
@;distinct from that of any other concept (or else they are actually the same concept);
@;a concept that fits all situations has no content and is useless;
@;and two concepts like OO and FP neither of which subsumes the other,
@;cover sets of situations neither of which is a subset of the other.
It makes no sense to oppose them, especially not when we see that
OO can be expressed in a few lines of FP, whereas
most modern OO languages contain FP as a subset.
The argument is actually a distortion of a legitimate question of OO design, @; TODO cite
wherein one has to decide whether some aspect of a class (respectively prototype or pattern)
embodied as slots or method functions, should be included directly in the class
(a) by inheriting from another class defining the aspect
(the class @emph{is-a} subclass of it — inheritance of classes), or
(b) indirectly by the class having a slot containing an object of that other class
(the class @emph{has-a} slot that is it —
composition of classes seen as object constructor functions).
The answer of course depends on expectations about how the class will be further specialized
within a static or dynamically evolving schema of data structures and algorithms.
If the schema is small, static, well-understood and won’t need to evolve,
it doesn’t really matter which technique is used to model it.
But as it grows, evolves and boggles the mind,
a more modular and incremental approach is more likely to enable adapting the software
to a changing situation, at which point thoughtful uses of inheritance can help a lot.@note{
@emph{Is} a car a chassis (inheritance),
or does it @emph{have} a chassis while not being it (composition)?
If you’re writing a program that is interested in the length of objects,
you may model a @c{car} as a @c{lengthy} object with a @c{length} slot,
and a @c{chassis} too. Now if your program will only ever be interested
but in the length of objects, you may altogether skip any object modelling:
and only use numeric length values directly everywhere for all program variables.
Is a car a chassis? Yes, they are both their length, which is the same number,
and you may unify the two, or let your compiler’s optimizer unify the two variables
as they get initialized them from the same computation.
Now if you know your program will evolve to get interested in
the width of objects as well as their length,
you might have records with length and width rather than mere numbers,
and still unify a car and its chassis.
But if your program eventually becomes interested in the height, weight or price of objects,
you’ll soon enough see that the two entities may somehow share some attributes
yet be actually distinct: ultimately, both @c{car} and @c{chassis} @emph{are} @c{lengthy},
but a @c{car} @emph{has} a @c{chassis} and @emph{is not} a @c{chassis}.}
@subsubsection{Encapsulation}
Many OO pundits claim that an essential concept in OO
is “encapsulation” or “information hiding”@~cite{DeRemerKron1975},
though there is no consensus as to what this or these concepts mean,
and no clear definition. @TODO{CITE}
Inasmuch as some people identify encapsulation as the presence
of specific visibility mechanisms
(with some slots or methods being public, private or something in–between),
we’ll easily dismiss the claim that it is an essential aspect of OO
by showing that many quintessential OO languages like Smalltalk or Common Lisp
lack any such specific mechanism,
whereas many non-OO languages possess mechanisms to achieve the same effect,
in the form of modules defining but not exporting identifiers
(e.g. not declaring them @c{extern} in C),
or simply lexical scoping as present in FP@~cite{rees1995}.
@TODO{cite Simula? JS?}
On the other hand, inasmuch as this “encapsulation” informally denotes
an aspect of modularity,
we’ll argue that the claim of encapsulation being essential to OO
partakes in our better formalized argument
according to which OO is about modularity (and incrementality).
See @seclink{modularity_and_incrementality}.
@subsubsection{Message Passing}
Alan Kay, who invented Smalltalk and coined the term “Object-Oriented Programming”
notably explained@~cite{Kay2020} that by that he originally meant
a metaphor of computation through independent (concurrent, isolated) processes
communicating by passing asynchronous messages.
This metaphor also guided the modifications originally
brought by Simula to Algol@~cite{Simula1966}.
However, neither Simula, nor Smalltalk nor any claimed “OO” language
actually fits that metaphor.
Instead, the only commonly used language ever to fit it
is Erlang@~cite{OOP2010};
yet Erlang is not part of the OO tradition, and its authors have instead
described its paradigm as “Concurrency-Oriented Programming”.
Meanwhile the theory of computation through message-passing processes
was studied with various “process calculi”,
that are also foreign to the OO tradition,
and largely unembraced by the OO community.
Moreover, many OO languages generalize and extend their method dispatch mechanism
from “single dispatch” to “multiple dispatch”@~cite{
bobrow86commonloops bobrow88clos CecilMultimethods};
their “multimethods” are attached to several objects or classes,
and there is no single object, class, or single independent entity of any kind
capable of either “receiving” or “sending” a message.
Mechanisms like typeclasses, while not usually considered part of the OO tradition,
can be seen as isomorphic to classes@~cite{LIL2012},
yet also lack any specific object to “receive” a message.
Thus, whatever historical role the paradigm of message-passing processes
may have had in inspiring the discovery of OO,
it remains a completely different paradigm,
with its own mostly disjoint tradition and very different concerns.
What is usually meant by OO, is a paradigm for organizing code development
for modularity and reuse, with a notable focus on “inheritance”
through classes or prototypes (or at times “patterns”),
usually in a synchronous evaluation framework within a single thread.
Whatever clear or murky correspondance between names and concepts others may use,
this paradigm is what we will call OO and discuss in this article,
systematically reducing it to elementary concepts.
@section[#:tag "modularity_and_incrementality"]{Modularity and Incrementality}
@subsection[#:tag "modularity"]{Modularity}
@subsubsection{Division of Labor}
Modularity@~cite{Parnas1972 Dennis1975} is the organization of software source code
in order to support division of labor, dividing it into “modules” that can each be
understood and worked on mostly independently from other modules.
@subsubsection{A Meta-linguistic Feature}
Most modern programming languages offer
@emph{some} builtin notion of modules as “second-class” entities,
entities that exist at compile-time but are not available as regular runtime values
A few languages even offer a notion of modules as “first-class” entities,
that can be manipulated as values at runtime.@note{
In between the two, some languages offer a “reflection” API that gives some often limited
runtime access to representations of the module entities.
This API is often limited to introspection only or mostly;
for instance, it won't normally let you call the compiler
to define new modules or the linker to load them.
YEt some languages support APIs to dynamically evaluate code,
that can be used to define new modules;
and some clever hackers find ways to call a compiler and dynamic linker,
even in languages that don’t otherwise provide support APIs for it.
}
But many (most?) languages offer no such notion;
indeed modules are a complex and costly feature to design and implement,
and few language designers and implementers will expend the necessary efforts toward it
at the start of language’s development.@note{
Unless they develop their language within an existing modular framework
for language-oriented programming, such as Racket,@TODO{cite. Also Stratego?}
from which they inherit the module system.
}
Yet modularity is foremost a @emph{meta-linguistic} concept:
even in a language that provides no support whatsoever for modules
@emph{within} the language itself (such as C),
programmers will find manual and automated means
to achieve and support modularity @emph{outside} the language. They will:
@itemize[
@item{copy and paste sections of code as poor man’s modules;}
@item{automate organized concatenation of code snippets with preprocessors;}
@item{divide code in files they can “transclude”, “link” or “load” together;}
@item{transclude “include” files in lieu of interfaces;}
@item{orchestrate building of software with utilities such as “make”;}
@item{bundle software into “packages” they exchange and distribute online;}
@item{create “package managers” to handle those bundles.}]
When for the sake of “simplicity”, “elegance”, or ease of development or maintenance,
support for modularity is lacking within a language, this language then becomes but
the kernel of a haphazard collection of tools cobbled together
to palliate the weakness of this kernel. The result inevitably ends up being
extremely complex, ugly, and hard to develop and maintain.
@subsubsection{Criterion for Modularity}
@principle{A design is modular if it enables developers to cooperate without having to coordinate},
compared to alternative designs that enable less cooperation or require more coordination,
given some goals for developers, a space of changes they may be expected to enact in the future, etc.
For instance, the object-oriented design of ASDF@~cite{ASDF2}
made it simple to configure, to extend, and
to refactor to use algorithms in @emph{O(n)} rather than @emph{O(n³)} or worse,
all of it without any of the clients having to change their code.
This makes it arguably more modular than its predecessor MK-DEFSYSTEM@~cite{kantrowitz1991}
that shunned use of objects (possibly for portability reasons at the time),
was notably hard to configure, and resisted several attempts to extend or refactor it.
@subsection[#:tag "incrementality"]{Incrementality}
@subsubsection{Small Changes}
Developers quickly lose direction, motivation, support from management
and buy-in from investors and customers when they do not have tangible results
to show for their work.
Incrementality is the ability for a system to
deliver more rewards for fewer efforts, compared to alternatives.
In other words, incrementality supports a short feedback loop in software development.
@subsubsection{A Developer-Interface Feature}
Incrementality should be understood within a framework of what changes
are or aren’t “small” for a human (or AI?) developer, rather than
for a fast and mindless algorithm. Otherwise, the most “incremental” design
would be to have code produced by @c{gunzip} or some similar decompressor,
that can expand a few bits of incremental change into a large amount of code.
Thus, for instance, changing some arithmetic calculations to use
bignums (large variable-size integers) instead of fixnums (builtin fixed-size integers)
in C demands a whole-program rewrite with a different program structure;
in Java involves some changes all over though straightforward and preserving the program structure;
in Lisp or Haskell requires no changes, or minimal and local.
Thus with respect to this and similar kinds of change, if expected,
Java has a more incremental design than C, but less than Lisp or Haskell.
There again, incrementality is usually a meta-linguistic notion, wherein
changes happen as pre-syntactic operations on the source code, rather than
semantic operations within the language itself. And yet, using reflection
and/or considering the entire “live” interactive development environment
as “the system” rather than a “dead” program in a programming language,
these pre-syntactic operations can be internalized.
@subsubsection{A Criterion for Incrementality}
@principle{A design is incremental if it enables developers
to enact change through small local modifications}
compared to alternative designs that require larger (costlier) rewrites
or more global modifications (or prohibit change, same as making its cost infinite).
@subsection[#:tag "incremental_modularity"]{Incremental Modularity}
@subsubsection{A Dynamic Duo}
Modularity and Incrementality work hand in hand:
@principle{Modularity means you only need to know
a small amount of old information to make software progress.
Incrementality means you only need to contribute
a small amount of new information to make software progress.}
Together they mean that a finite-brained developer
can make more software progress with a modular and incremental design
than with a less-modular and less-incremental design.
@subsubsection{Reducing Costs vs Moving them Around}
Beware that many designs have been wrongfully argued as
more modular and/or incremental based on moving code around:
these myopic designs achieve modest development savings in a few modules under focus
by vastly increasing the development costs left out of focus,
in extra boilerplate and friction, in other modules having to adapt,
inter-module glue being made harder, or module namespace curation getting more contentious.
For instance microkernels or microservices may make each “service” look smaller,
but only inasmuch as the overall code has been butchered into parts
between which artificial runtime barriers were added;
yet each barrier added involves extra code, actually increasing the incidental
complexity of the code in direct proportion to the alleged benefits,
without doing anything whatsoever to address its intrinsic complexity.
These misguided designs stem from the inability to think about meta-levels
and distinguish between compile-time and runtime organization of code.
@subsubsection{Incremental Modularity, Interactively}
Incrementality does not necessarily mean that a complex addition or refactoring
can be done in a single small change;
rather, code evolution can be achieved in many small changes, wherein
the system can assist the developer into only having to care
about a small change at a time, while the system tracks down what are all
the small remaining changes necessary.
For instance, a rich static type system can often be used as a tool
to guide large refactorings by dividing them in manageably small changes,
making the typechecker happy one redefinition at a time after a type modification.
This example also illustrates how
@principle{Incrementality and Modularity usually happen through
meta-linguistic mechanisms rather than linguistic mechanisms},
i.e. through tooling outside the language rather than
expressions inside the language.
@section{Prototypes}
@subsection[#:tag "internal_incremental_modularity"]{Internal Incremental Modularity}
@subsubsection{Internalized Feature}
Now what if modular increments of computational specifications could be
embodied as linguistic expressions @emph{within} a programming language,
that could be manipulated at runtime and studied formally,
rather than just as semi-formal meta-linguistic interactions?
@principle{We dub @emph{prototype} such an embodiment
of incremental modularity within a language}.
And to narrow the discussion down to a formal context,
let’s consider programming languages with a functional programming core,
i.e. that contain some variant of the lambda-calculus as a fragment,
either untyped or with suitably expressive types (to be determined later).
@subsubsection{Embodying Specification}
To embody some concept in the functional programming core of a language that has one,
you will necessarily use a function.
Since the concept is the specification of a computation,
the function must eventually return that specific computation as an output value,
given some inputs to be determined.
The type of its output is the type of the target value.
@subsubsection{Embodying Modularity}
Each prototype should be able to
contribute information that other modules can use while
using information from other modules it depends on.
In functional terms, it will be or contain a function with
the former among its outputs and the latter among its input.
Now to maximize the expressiveness of this Modularity in a functional setting,
a prototype specifying one aspect of a computation should be able to make
(forward) references to the complete computation being specified itself,
so as to pass it as argument to higher-order functions extracting information
about arbitrary aspects of it.
This means the prototype should be or contain a function
with the computation @c{self} as input for self-reference,
and returns as output a computation with the specified structure
that uses @c{self} in an @emph{open recursion} for all “self-reference”
to aspects the final computation (possibly further refined, extended or overridden).
That function then specifies (part of)
a larger specification function of which the complete computation will be
a @emph{fixed-point}.
@subsubsection{Embodying Incrementality}
Each prototype should be able to refer not only to
the complete computation with all available information, but also to
the partial computation with only the information specified @emph{so far}.
Thus, it may examine so-far specified aspects and use them to
contribute small modifications to these existing aspects as well as
new aspects based on this information.
In functional terms, the prototype function will take
an additional input @c{super} based on which to specify a computation.
Thus, to embody incremental modularity, a prototype will be or contain
a prototype function of @c{self} and @c{super} returning an enriched @c{self}.
@TODO{
Mixins: The simplest of OO models, pure functional prototypes using mixin inheritance,
and how its (λ (super self) ...) pattern directly maps to Incrementality and Modularity,
or to Ad Hoc polymorphism and Open Recursion.}
@subsubsection{Prototype Primitives}
Prototypes of course depend on whichever primitive operations support
the type of computation being specified;
but those are not specific to prototypes as such.
The minimal set of prototype-specific primitives follows:
@itemize[
@item{A function that given a prototype specifying a computation
(and possibly some context) returns a complete computation
exactly as specified, closing the open recursion;
this function we call @c{instantiate}, or @c{fix}
(for reasons that will soon be obvious).
}
@item{A function to compose, chain, juxtapose and/or cross-reference
multiple smaller prototypes (at least two, maybe more)
each specifying some aspects of a computation,
return a larger prototype that contains all these combined aspects,
yet ready to be further composed, keeping the recursion open;
this function we call @c{mix}, or @c{inherit}
(for reasons that will also soon be obvious)}]
@subsection[#:tag "simplest_prototypes"]{Simplest prototypes}
@subsubsection[#:tag "mixin_functions"]{Mixin Functions}
The very simplest possible design for @emph{prototypes}
is thus as “mixin” functions with the following minimal type:
@Code{Mixin self super = self ⊂ super ⇒ self → super → self}
where @c{self} is the type of the computation as completely specified,
@c{super} the type of the computation as partially specified so far,
@c{self ⊂ super ⇒} is the constraint that @c{self} should be a subtype of @c{super},
and @c{Mixin} is the name introduced by Cannon@~cite{Cannon82}
and reprised and popularized by Cook and Bracha@~cite{bracha1990mixin}.
The mixin instantiation and inheritance primitives are as follows:
@Code{
type Mixin inherited referenced defined =
inherited → referenced → inherited⋂defined
build :: top → Mixin top target target → target
build = λ base mixin ↦ Y (mixin base)
inherit :: Mixin i1 r1 d1 → Mixin i2⋂d1 r2 d2 → Mixin i1⋂i2 r1⋂r2 d1⋂d2
inherit = λ parent child super self ↦ child (parent super self) self
}
@subsubsection{Elucidating Mixin Instantiation}
The @c{build} function above computes a fixed-point @c{target}
for a @c{mixin} given as extra argument a type-appropriate @c{base} value
that serves as seed of the computation being instantiated:
an empty record @c|{{}}|, a function that always fails @c{⊤ = λ _ ↦ ⊥}, etc.
The type of @c{base}, a.k.a. @c{top}, is thus
a base type for the specified computation:
a supertype of the type @c{instance} being computed, a.k.a. @c{self}.
In a monomorphic setting, @c{base} is just @c{instance} itself;
with a rich-enough type system, it can be a “top” type
for many distinct types of computations, carrying no information.
The @c{Y} combinator is the usual fixed-point combinator, chosen to match
the variant of λ-calculus being used (e.g. using eager or lazy evaluation).
@;TODO explaining footnote or citation.
@;The definition matches the @c{fix} function from the introduction
@;modulo α-renaming, well-named since its essence is to extract a fixed-point.
@subsubsection{Elucidating Mixin Inheritance}
Mixin inheritance combines two @emph{mixins} @c{child} and @c{parent}
into one that given two @emph{instances} @c{instance} and @c{inherited}
passes @c{(parent instance inherited)} as the @c{super} argument to @c{child}.
By the time the complete @c{instance} and @c{inherited} value so far
are provided (if ever), the combined mixin itself may be but part of
a wider combination, with further mixins both to the right and to the left.
The provided @c{instance} will then be the fixed-point of
the entire wider combination (involving further children to the left,
then @c{child} and @c{parent}, then further parents to the right).
Meanwhile, the @c{inherited} value will only contain the information from
applying the further parent mixins to the right to the provided @c{base} object.
The @c{parent} will be able to extend (enrich or override)
any method definition from the @c{inherited} computation;
the @c{child} may further extend it, and further mixins to the left yet more.
The function matches the @c{mix} function from the introduction
modulo α-renaming, well-named since its essence is to compose or “mix” mixins.
The function is associative, with identity mixin @c{idm = λ s t ↦ t}.
As usual, a change of representation from @c{p} to @c{cp = inherit p}
would enable use regular function composition for @c{mix},
whereas @c{fix} would retrieve @c{p} as @c{cp idm};
but that would make the types unnecessarily more complex.
@; many isomorphic ways: change the order of super and self,
@; use fix and mix, or cfix and idm as basic combinators, etc.
@subsubsection[#:tag "stricter_types"]{Stricter, More Modular Types}
The types given in @seclink{mixin_functions} work well,
but then must be carefully chosen so the @c{self} and @c{super}
used during mixin definition should precisely match those used
during mixin composition and instantiation.
This is not a problem if a mixin is used only once
(as in single inheritance, see @seclink{single_inheritance}),
but it is a problem in the more general case of mixin inheritance
(and in multiple inheritance, see @seclink{multiple_inheritance}).
A more refined type that can be used for mixins is then:
@Code{Mixin inherited referenced defined =
∀ super ⊂ inherited ⇒
super → referenced → super⋂defined}
where @c{inherited} is the type intrinsic to the mixin
indicating which inherited methods from the super argument are actually being used,
whereas @c{super} will be the set of methods effectively defined
in the super argument, depending depending on the context of instantiation.
This type is an intersection of all variants of the previous type
for subtypes @c{eself} and @c{esuper} of @c{self} and @c{super} respectively.
It allows a mixin to be defined in its most general form,
then used multiple times, each in a distinct more specialized context,
making the mixin definition and its typechecking @emph{more modular}.
In exchange for this modularity, the mixin is restricted
to only act in a uniform manner, that monotonically preserves
arbitrary additional information passed as arguments to it.
@; For instance, the mixin is not allowed to query which set of fields
@; will be effectively used in the super in practice to decide
@; which fields it will itself define.
@; It is not allowed to rename fields from the super, etc.
@; Try with higher kinds for self and super, so it’s structurally required
@; that the mixin should use the eself parameter for reference,
@; and return an extended super for its structure?
@subsubsection[#:tag "minimal_design_maximal_outreach"]{Minimal Design, Maximal Outreach}
We have just derived from first principles a minimal design
of prototypes-as-mixin-functions
to embody modular increments of software specification
inside a functional programming language.
And this design closely reproduces that of existing models and languages:
@itemize[
#:style enumparenalph
@item{It reproduces the earliest general semantic model of OO@~cite{bracha1990mixin}.}
@item{It also reproduces the formal semantics (though not the implementation) of objects
in the pure lazy dynamic functional prototype object language Jsonnet@~cite{jsonnet},
a popular choice to generate distributed software deployment configurations
for Kubernetes or AWS, and was started as a conceptual cleanup of}
@item{the Google Control Language GCL@~cite{gclviewer2008} (née BCL, Borg Control Language),
which has been used to specify all of Google’s distributed software deployments
since about 2004 (but uses dynamic rather than static scoping,
causing dread among Google developers).}
@item{It furthermore reproduces not just the semantics but the actual implementation
of “extensions”@~cite{nix2015} as a user-level library
in the pure lazy dynamic functional language Nix;
these extensions are heavily used by NixOS@~cite{dolstra2008nixos},
a Nix-based software distribution for Linux and macOS, one with thousands of contributors.@note{
These extensions were reinvented semi-independently by Peter Simons,
who did not know anything about their relationship to Prototypes, Mixins or OO,
but was inspired by examples by and discussions with Andres Löh and Conor McBride,
who were more versed in this literature.
}}]
@; TODO see if NixOps, DisNix, flakes, use extensions or a variant thereof, if so mention it.
The main difference between our minimal model and the above works is that
our model generalizes them by not being tied to any specific encoding of records,
or indeed to records at all (see @seclink{instances_beyond_records})
This simplest of object-oriented designs,
purely functional prototypes as mixin functions,
has thus been proven capable to literally support
specification and deployment of software on a world-wide scale.
As we’ll see, this design embodies the primitive core of OO,
to which other forms of OO can be reduced.
In the end, we can rightfully claim that the essence of OO
in historical intent as well as practical extent is
the incremental modularity embodied as language entities,
and that prototypes are the most direct form of this embodiment.
@TODO{cite to substantiate}
@subsection{Working with Records}
@subsubsection{Records, Methods, Instances}
Most OO tradition, including the precedents cited above, follows
the historical restriction of only enabling modular and incremental specification of
@emph{“records”} mapping names to values@~cite{hoare1965record Cook1989}.
The names, the values they are bound to, and/or the bindings,
are at times called @emph{“methods”}, “slots”, “fields”, “attributes”, “properties”, “members”,
“variables”, or otherwise, depending on the specific sub-tradition.
The records themselves will be suitably wrapped into a proper computation result @emph{instance}:
a class (in Class OO),
an object (in Prototype OO),
a typeclass (in FP with typeclasses, though its users may deny the OO tradition),
wherein the record will embody the “method dispatch table”,
“attribute set”, “dictionary” or whatchamacallit of the aforementioned entity.
Note that this meaning of the word @emph{instance} itself comes from the Prototype OO tradition,
and does not match what the meaning of the word in the class OO tradition;
in the latter tradition, “instance” instead refers to an element of the class seen as a type,
whereas that type would be the instance in the prototype OO tradition.
For now we will focus on the simplest and most primitive kind of OO, Prototype OO,
in its simplest form where the instances are the records themselves.
We will extend our point of view in @seclink{inheritance} and later.
@subsubsection[#:tag "encoding_records"]{Encoding Records}
We will assume that, either with some language primitives,
some “builtin modules” to import from,
or some variant of Church encoding, our Functional Language
is suitably extended with the usual essential data structures:
numbers, booleans, strings, tuples, lists.
Record keys can be of a language-appropriate type with a decidable equality predicate:
integers (sometimes as named constants at the meta-level),
strings, or optionally symbols (interned strings) or
identifiers (source code tracking entities).
Records can be defined from the empty record @c{rtop} and
a constructor @c{rcons k v r} that given a key @c{k}, a value @c{v} and
a previous record @c{r} returns a new record that extends @c{r}
with a new or overriding binding of @c{k} to @c{v}.
The three simplest encodings of a record would then be
as a function, an @emph{alist}, or a mapping table, as follow.
Records as functions is the simplest encoding, and
accessing the value for a key is done by just calling the function with the key.
However, overriding and deletion will leak memory and access time;
also they don’t support iteration over bindings —
an introspection operation that is very much desired in contexts like I/O automation,
though best kept hidden in contexts like analysis or restriction of software effects.
The two constructors are as follows:
@Code|{ftop = ⊤ = λ _ ↦ ⊥
fcons = λ k v r m ↦ if m == k then v else r m}|
The traditional Lisp “alist” (association list) data structure,
singly-linked list of (key,value) pairs,
solves the previous encoding’s issues with memory leak and lack of introspection,
but is still inefficient with linear-time operations.
Its two constructors are as follows:
@Code|{atop = []
acons = λ k v r ↦ [(k,v), ...r]}|
Records as pure mapping tables can provide logarithmic-time operations;
but their implementation can be complex if not provided as a language primitive.
Binding accessor, binding presence test, binding deletion, etc.,
are left as an exercise to the reader.
We will write their constructors as follows:
@Code|{mtop = {}
mcons = λ k v r ↦ {k: v, ...r}}|
In our previous article@~cite{poof2021} we showed how you could start with
a simple of records as function, use OO style to incrementally and modularly specify
a more elaborate mapping table data structure, and thereafter use that data structure
in the definition of more efficient further records.
That’s our first case of a “meta-object protocol”@~cite{amop}, one that illustrates
how to @emph{bootstrap} more elaborate variants of OO from simpler variants.
@subsubsection{Mixins and Helpers for Records}
Abstracting over the specific encoding for records,
the primitive way to define a mixin that adds a method to a record being specified is with:
@Code{methodG = λ rkons k f s t ↦ rkons k (f s t) t}
wherein the argument @c{k} is a key naming the method,
@c{f} is a function that takes the instance @c{s} of type @c{self} and
a inherited record @c{t} of type @c{super} and returns a value @c{v}
to which to bind the method in a record that extends the inherited record,
according to the record encoding defined by @c{rkons}.
In practice, OO language implementations provide a fixed builtin encoding for records,
with specialized instantiation function @c{fixR} and method-addition mixin @c{methodR}:
@Code{fixR = λ mixin ↦ fix mixin rtop
methodR = methodG rcons}
For a mixin that binds a method to a constant value @c{v}, you can then use
@Code{methodK k v = methodR k (λ _ _ ↦ v)}
Common helpers could similarly be defined for mixins that bind a method to a value
that only depends on the instance @c{s} of type @c{self}
and not the inherited value @c{t} of type @c{super}, or vice versa.
Further helpers could help define more than one method at once
e.g. by somehow appending record contents rather than consing bindings one at a time.
Furthermore, given macros in the base language,
specialized syntax could help make such definitions concise.
With or without macros, we will assume a syntax @c{a.b}
for calling an appropriate record accessor with record @c{a}
and method name @c{b} suitably encoded as a key.
For simplification purposes, we will hereafter assume method names are strings.
Meanwhile, we will assume the following helpers to handle lists of mixins
without having to awkwardly nest lots of applications of the @c{mix} function,
assuming bracketed and comma-delimited lists, with @c{[head, ...tails]} patterns:
@Code{mix* [] = idm
mix* [h, ...t] = mix h (mix* t)
fix* base l = fix base (mix* l)
fixR* = fix* rtop}
Giving polymorphic types to these list helpers may require not only subtyping
but also some form of type indexing for those lists.
Doing it without requiring full dependent types is left as an exercise to the reader.
@subsubsection{Example Records built from Mixins}
We can now define the usual point and colored-point example as follows,
where @c{$point} is the @emph{prototype} for the point
(in our simplest prototypes-as-mixin model),
and @c{point} its @emph{instance}:
@Code{$point = mix (methodK "x" 3.0) (methodK "y" 4.0)
point = fixR $point
$blue = (methodK "color" "blue")
coloredPoint = fixR* [$blue, $point]}
Assuming a primitive @c{assert} that checks that a boolean value is true,
and an equality predicate that behaves properly for records,
we can then assert:
@Code|{assert (point == {x: 3.0, y: 4.0})
assert (coloredPoint == {x: 3.0, y: 4.0, color: "blue"})}|
We can further define and use a radius-defining mixin,
assuming functions @c{sqr} and @c{sqrt} for square and square roots of numbers respectively:
@verbatim|{$radius == methodR "radius" λ s _ ↦ sqrt ((sqr s.x) + (sqr s.y))
pointWithRadius = fixR* [$radius, $point]
assert (pointWithRadius == {x: 3.0, y: 4.0, radius: 5.0})}|
@subsubsection{Mixin Caveats}
Note that in the above examples,
all the mixins commute, and we could have changed the order in which we define those methods
— because they never use inheritance nor overrode any method, and
instead pairwise define disjoint sets of methods.
Thus @principle{merging disjoint commuting mixins embodies modularity, but not incrementality}:
incrementality can still be achieved in an extralinguistic way by
rebuilding modules in different ways from smaller modules;
but to achieve it intralinguistic, you need a way to operate on existing modules,
which by definition is not commutative.
As a counterpoint, the mixins below do override or inherit previous method bindings,
and therefore do not commute, and instead yield different results when mixed in different orders:
@Code|{$v1 = methodK "v" 1
$v2 = methodK "v" 2
$v10 = methodR "v" λ _ t ↦ t.v * 10
assert (fixR* [$v1,$v2] == {v: 1})
assert (fixR* [$v2,$v1] == {v: 2})
assert (fixR* [$v1,$v10] == {v: 1})
assert (fixR* [$v10,$v1] == {v: 10})}|
Finally note that trying to instantiate @c{$v10} alone would fail:
it would try to multiply by 10 the inherited value of @c{v},
but the base record @c{rtop} has no such value and this would result in an error.
Even without inheritance, the prototype @c{$radius} above would also fail to instantiate alone,
because it will try to access undefined methods @c{x} and @c{y}.
This illustrates how not every prototype can be successfully instantiated,
which is actually an essential feature of prototypes
(whether implemented as simple mixins or not),
since the entire point of a prototype is to provide a @emph{partial} specification
of a small aspect of an overall computation,
that in general depends on other aspects being defined by other prototypes.
@section[#:tag "inheritance"]{Mixin, Single, and Multiple Inheritance}
@subsection{Mixin Inheritance}
@subsubsection{The Last Shall Be First}
The inheritance@~cite{inheritance1996} mechanism described above
is called @emph{mixin inheritance}.
It is arguably the simplest kind of inheritance to formalize @emph{given the basis of FP}.
It also maps directly to the concepts of Modularity and Incrementality we are discussing.
And for these reasons we introduced it first.
However, historically it was discovered last, because FP wasn’t mature
until much after the time the need for Modularity and Incrementality was felt.
It is also relatively more obscure, probably because, in addition to the above,
it is less modular than the more complex but previously discovered
multiple inheritance (discussed below in @seclink{multiple_inheritance}).
And yet, we already saw above in @seclink{minimal_design_maximal_outreach} that
object prototypes with mixin inheritance are used to specify software configurations at scale.
An elaborate form of mixin inheritance is also notably used in the class-based OO system
used by Racket’s GUI@~cite{Flatt06schemewith}.
@subsubsection{Mixin Semantics}
We saw above (@seclink{simplest_prototypes}) that mixin inheritance involves just
one type constructor @c{Mixin} and two functions @c{fix} and @c{mix}:
@Code{Mixin self super = self ⊂ super ⇒ self → super self
fix : Mixin self top → top → self
fix = λ mixin top ↦ Y (λ self ↦ mixin self top)
mix : Mixin self super → Mixin super duper → Mixin self duper
mix = λ child parent self duper ↦ child self (parent self duper)}
@subsection[#:tag "single_inheritance"]{Single inheritance}
@subsubsection{Simple and Efficient}
Historically, the first inheritance mechanism discovered was @emph{single inheritance},
though it was not known by that name until later.
In an influential 1965 paper@~cite{hoare1965record},
Hoare introduced the notions of “class” and “subclass” of records
(as well as, infamously, @emph{null}).
Subclasses though were first implemented in @~cite{Simula1968},
using a previous class as a “prefix”, reusing all its field definitions and method functions;
the text of the resulting class is then the “concatenation”
of the direct text of all its transitive @emph{prefix classes}.
In modern terms, we call the prefix a superclass. @; TODO CITE
Single inheritance was later adopted by Smalltalk-76 @;@~cite{Smalltalk} @;TODO FIX ME
and many other contemporaneous systems,
and later made especially popular circa 1995 by Java. @;@~cite{}. @TODO{or C#}
Single inheritance is easy to implement without higher-order functions;
method lookup can be compiled into a simple and efficient array lookup at a fixed index
— as opposed to some variant of hash-table lookup in the general case
for mixin inheritance or multiple inheritance.
In olden days, when resources were scarce, and before FP was mature,
these features made single inheritance more popular
than the more expressive but costlier alternatives.
Even some more recent languages that support multiple inheritance (@seclink{multiple_inheritance})
also support single inheritance for some classes (or “structures”),
and sometimes the consistent combination of the two
(@seclink{single_and_multiple_inheritance_together}).
@subsubsection{Semantics of Single Inheritance}
In single inheritance, the prototypes at stake,
i.e. the entities that embodied increments of modularity,
are not the mixin functions of mixin inheritance,
but simpler @emph{generators} that only take a @c{self} as open recursion parameter
and return a record using @c{self} for self-reference.
The semantics can reduced to the following types and functions:
: @; TODO CITE Cook
@Code{Gen self = self → self
Y : Gen self → self
base : Gen top → top
base = λ _ ↦ rtop
extend : Mixin self super → Gen super → Gen self
extend = λ mixin parent self ↦ mixin self (parent self)}
@; = λ mixin parent self ↦ (mix mixin λ self _ ↦ parent self) self base
Note how @c{Gen self} is the type of generators for instances of type @c{self};
the instantiation function for a generator is the usual fixed-point combinator @c{Y};
the @c{base} object to extend is the generator that always returns the empty record
(for whichever encoding is used for records);
and the @c{extend} function creates a child generator from a parent generator
and a mixin (as in mixin inheritance above), where @c{self} is constrained
to be a subtype of @c{super}.
Mind again that in the single-inheritance paradigm,
@emph{the prototype is the generator, not the mixin}.
A prototype-as-generator may thus be the @c{base} generator
that returns the empty record @c{rtop} or otherwise base instance,
or a generator created by extending
a @emph{single} @c{parent} generator with a @c{mixin}.
Since the same constraint applies recursively to the parent generator,
a prototype-as-generator can be seen as repeatedly extending that @c{base} generator
with an ordered list of mixins to compose.
Just like in mixin inheritance, an @emph{instance} can thus still be seen as
the fixed point of the composition of a list of elementary mixins
as applied to a base instance.
However, since generators, not mixins, are the prototypes,
the “native” view of single inheritance is more to see the parent specified in @c{extend}
as a direct super prototype, and the transitive supers-of-supers as indirect super prototypes;
each prototype is considered as not just the mixin it directly contributes,
but as the list of all mixins directly and indirectly contributed.
@subsubsection{Single Inheritance with Second-Class Mixins}
While single-inheritance requires some form of mixin,
most single-inheritance object systems don’t allow mixins as