Basic object model in Scheme revisited
Table of Contents
% Latex Preamble definitions here (mostly usepackage)
\usepackage%
%[dvipsnames]
{xcolor}
% make sure this is before the loading font packages
\newcommand\hmmax{0}
\newcommand\bmmax{0}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage
%[dvipsnames]
{graphicx}
\usepackage{float}
%\usepackage[numbers]{natbib}
\usepackage[document]{ragged2e}
%
% enumitem doesn't seem to work with beamer
%\usepackage[inline]{enumitem}
\usepackage{wrapfig}
\usepackage{stackrel}
% extensible arrows
\usepackage{extpfeil}
% \usepackage{trfrac}
\usepackage{amsthm}
\usepackage{tikz}
\usepackage{tikz-cd}
\usepackage{tikz}
\usepackage{tikz-qtree}
\usetikzlibrary{automata, positioning, arrows, shapes.geometric}
\usepackage{turnstile}
\usepackage{comment}
%https://tex.stackexchange.com/questions/21334/is-there-a-package-that-has-the-clockwise-gapped-circle-arrow-in-it
% \usepackage{mathbx}
\usepackage{datetime}
\usepackage{datetime2}
%% Also See
%% http://u.cs.biu.ac.il/~tsaban/Pdf/LaTeXCommonErrs.pdf
%% for general tips
\usepackage{listings}
\usepackage{subfigure}
\usepackage{bm}
\usepackage{amsfonts} %% - also included by amssymb
\usepackage{mathpazo} %% - because the OP uses mathpazo, optional
%\usepackage{tufte-latex}
\usepackage{comment}
\usepackage{mathtools}
\usepackage{bussproofs}
\usepackage{hyperref}
%\usepackage{cleveref}
%% Your math definitions here
% \newcommand{\alphaequiv}{{\underset{\raise 0.7em\alpha}{=}}}
\newcommand{\yields}{\Rightarrow}
\newcommand{\derives}{\overset{*}{\yields}}
\newcommand{\alphaequiv}{=_{\alpha}}
\newcommand{\tto}[2]{{\overset{#1}{\underset{#2}{\longrightarrow}}}}
\newcommand{\transitsto}[2]{{\overset{#1}{\underset{#2}{\longrightarrow}}}}
\newcommand{\xtransitsto}[2]{{\underset{#2}{\xrightarrow{#1}}}}
\newcommand{\xtransitsfrom}[2]{{\underset{#2}{\xleftarrow{#1}}}}
\newcommand{\xto}[2]{{\xtransitsto{#1}{#2}}}
\newcommand{\xfrom}[2]{{\xtransitsfrom{#1}{#2}}}
\newcommand{\xreaches}[2]{{\underset{#2}{\xtwoheadrightarrow{#1}}}}
\newcommand{\reaches}[2]{{\underset{#2}{\xtwoheadrightarrow{#1}}}}
%\newcommand{\reaches}[2]{{\overset{#1}{\underset{#2}{\twoheadrightarrow}}}}
%\newcommand{\goesto}[2]{\transitsto{#1}{#2}}
%\newcommand{\betareducesto}{{\underset{\beta}{\rightarrow}}}
\newcommand{\betareducesto}{\rightarrow_{\beta}}
%\newcommand{\etareducesto}{{\underset{\eta}{\rightarrow}}}
\newcommand{\etareducesto}{\rightarrow_{\eta}}
%\newcommand{\betaetareducesto}{{\underset{\beta\ \eta}{\rightarrow}}}
\newcommand{\betaetareducesto}{\rightarrow_{\beta\eta}}
\newcommand{\preducesto}{\rhd}
\newcommand{\psimplifiesto}{\stackrel{\scriptstyle{*}}{\rhd}}
\newcommand{\lreducesto}{\rightsquigarrow}
\newcommand{\lsimplifiesto}{\stackrel{\scriptstyle{*}}{\lreducesto}}
\newcommand{\rewritesto}{\hookrightarrow}
\newcommand{\goesto}[1]{\stackrel{#1}{\rightarrow}}
\newcommand{\xgoesto}[1]{\xrightarrow{#1}}
\newcommand{\reducesto}{\stackrel{}{\rightarrow}}
\newcommand{\simplifiesto}{\stackrel{\scriptstyle{*}}{\rightarrow}}
\newcommand{\connected}[1]{\stackrel{#1}{\leftrightarrow}}
\newcommand{\joins}{\downarrow}
\newcommand{\evaluatesto}{\Longrightarrow}
%\newcommand{\lit}[1]{\hbox{\sf{#1}}}
\newcommand{\lit}[1]{{\sf{#1}}}
\newcommand{\true}{\lit{true}}
\newcommand{\false}{\lit{false}}
\def\Z{\mbox{${\mathbb Z}$}}
\def\N{\mbox{${\mathbb N}$}}
\def\P{\mbox{${\mathbb P}$}}
\def\R{\mbox{${\mathbb R}$}}
\def\T{\mbox{${\mathbb T}$}}
\newcommand{\Rp}{{\mathbb{R}}^+}
\def\Bool{\mbox{${\mathbb B}$}}
\def\Q{\mbox{${\mathbb Q}$}}
\def\sA{\mbox{${\cal A}$}}
\def\sB{\mbox{${\cal B}$}}
\def\sC{\mbox{${\cal C}$}}
\def\sD{\mbox{${\cal D}$}}
\def\sF{\mbox{${\cal F}$}}
\def\sG{\mbox{${\cal G}$}}
\def\sL{\mbox{${\cal L}$}}
\def\sP{\mbox{${\cal P}$}}
\def\sM{\mbox{${\cal M}$}}
\def\sN{\mbox{${\cal N}$}}
\def\sR{\mbox{${\cal R}$}}
\def\sS{\mbox{${\cal S}$}}
\def\sO{\mbox{${\cal O}$}}
\def\sT{\mbox{${\cal T}$}}
\def\sU{\mbox{${\cal U}$}}
\def\th{\mbox{$\widetilde{h}$}}
\def\tg{\mbox{$\widetilde{g}$}}
\def\tP{\mbox{$\widetilde{P}$}}
\def\norm{\mbox{$\parallel$}}
\def\osum{${{\bigcirc}}\!\!\!\!{\rm s}~$}
\def\pf{\noindent {\bf Proof}~~}
\def\exec{\mathit{exec}}
\def\Act{\mathit{A\!ct}}
\def\Traces{\mathit{Traces}}
\def\Spec{\mathit{Spec}}
\def\uns{\mathit{unless}}
\def\ens{\mathit{ensures}}
\def\lto{\mathit{leads\!\!-\!\!to}}
\def\a{\alpha}
\def\b{\beta}
\def\c{\gamma}
\def\d{\delta}
\def\sP{\mbox{${\cal P}$}}
\def\sM{\mbox{${\cal M}$}}
\def\sA{\mbox{${\cal A}$}}
\def\sB{\mbox{${\cal B}$}}
\def\sC{\mbox{${\cal C}$}}
\def\sI{\mbox{${\cal I}$}}
\def\sS{\mbox{${\cal S}$}}
\def\sD{\mbox{${\cal D}$}}
\def\sF{\mbox{${\cal F}$}}
\def\sG{\mbox{${\cal G}$}}
\def\sR{\mbox{${\cal R}$}}
\def\tg{\mbox{$\widetilde{g}$}}
\def\ta{\mbox{$\widetilde{a}$}}
\def\tb{\mbox{$\widetilde{b}$}}
\def\tc{\mbox{$\widetilde{c}$}}
\def\tx{\mbox{$\widetilde{x}$}}
\def\ty{\mbox{$\widetilde{y}$}}
\def\tz{\mbox{$\widetilde{z}$}}
\def\tI{\mbox{$\widetilde{I}$}}
\def\norm{\mbox{$\parallel$}}
\def\sL{\mbox{${\cal L}$}}
\def\sM{\mbox{${\cal M}$}}
\def\sN{\mbox{${\cal N}$}}
\def\th{\mbox{$\widetilde{h}$}}
\def\tg{\mbox{$\widetilde{g}$}}
\def\tP{\mbox{$\widetilde{P}$}}
\def\norm{\mbox{$\parallel$}}
\def\to{\rightarrow}
\def\ov{\overline}
\def\gets{\leftarrow}
\def\too{\longrightarrow}
\def\To{\Rightarrow}
%\def\points{\mapsto}
%\def\yields{\mapsto^{*}}
\def\un{\underline}
\def\vep{$\varepsilon$}
\def\ep{$\epsilon$}
\def\tri{$\bigtriangleup$}
\def\Fi{$F^{\infty}$}
\def\Di{\Delta^{\infty}}
\def\ebox\Box
\def\emp{\emptyset}
\def\leadsto{\rightharpoondown^{*}}
\newcommand{\benum}{\begin{enumerate}}
\newcommand{\eenum}{\end{enumerate}}
\newcommand{\bdes}{\begin{description}}
\newcommand{\edes}{\end{description}}
\newcommand{\bt}{\begin{theorem}}
\newcommand{\et}{\end{theorem}}
\newcommand{\bl}{\begin{lemma}}
\newcommand{\el}{\end{lemma}}
% \newcommand{\bp}{\begin{prop}}
% \newcommand{\ep}{\end{prop}}
\newcommand{\bd}{\begin{defn}}
\newcommand{\ed}{\end{defn}}
\newcommand{\brem}{\begin{remark}}
\newcommand{\erem}{\end{remark}}
\newcommand{\bxr}{\begin{exercise}}
\newcommand{\exr}{\end{exercise}}
\newcommand{\bxm}{\begin{example}}
\newcommand{\exm}{\end{example}}
\newcommand{\beqa}{\begin{eqnarray*}}
\newcommand{\eeqa}{\end{eqnarray*}}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}
\newcommand{\bcent}{\begin{center}}
\newcommand{\ecent}{\end{center}}
% \newcommand{\la}{\langle}
% \newcommand{\ra}{\rangle}
\newcommand{\bcor}{\begin{corollary}}
\newcommand{\ecor}{\end{corollary}}
\newcommand{\bds}{\begin{defns}}
\newcommand{\eds}{\end{defns}}
\newcommand{\brems}{\begin{remarks}}
\newcommand{\erems}{\end{remarks}}
\newcommand{\bxrs}{\begin{exercises}}
\newcommand{\exrs}{\end{exercises}}
\newcommand{\bxms}{\begin{examples}}
\newcommand{\exms}{\end{examples}}
\newcommand{\bfig}{\begin{figure}}
\newcommand{\efig}{\end{figure}}
\newcommand{\set}[1]{\{#1\}}
\newcommand{\pair}[1]{\langle #1\rangle}
\newcommand{\tuple}[1]{\langle #1\rangle}
\newcommand{\size}[1]{| #1 |}
\newcommand{\union}{\cup}
\newcommand{\Union}{\bigcup}
\newcommand{\intersection}{\cap}
\newcommand{\Intersection}{\bigcap}
\newcommand{\B}{\textbf{B}}
%\newcommand{\be}[2]{\begin{equation} \label{#1} \tag{#2} \end{equation}}
\newcommand{\abs}[1]{{\lvert}#1{\rvert}}
\newcommand{\id}[1]{\mathit{#1}}
\newcommand{\pfun}{\rightharpoonup}
\newcommand{\ra}[1]{\kern-1.5ex\xrightarrow{\ \ #1\ \ }\phantom{}\kern-1.5ex}
\newcommand{\ras}[1]{\kern-1.5ex\xrightarrow{\ \ \smash{#1}\ \ }\phantom{}\kern-1.5ex}
\newcommand{\da}[1]{\bigg\downarrow\raise.5ex\rlap{\scriptstyle#1}}
\newcommand{\ua}[1]{\bigg\uparrow\raise.5ex\rlap{\scriptstyle#1}}
% \newcommand{\lift}[1]{#1_{\bot}}
\newcommand{\signal}[1]{\tilde{#1}}
\newcommand{\ida}{\stackrel{{\sf def}}{=}}
\newcommand{\eqn}{\doteq}
\newcommand{\deduce}[1]{\sststile{#1}{}}
%% These don't sit very well with MathJax
%% so we don't plan to use theorem like environments
%% in org documents.
%% instead we plan to use headings with
%% 1. property drawers with a CLASS property identifying
%% the environment
%% 2. A tag with the same name as the CLASS property
%% In LaTeX export, these turn into (sub)sections.
%% See http://u.cs.biu.ac.il/~tsaban/Pdf/LaTeXCommonErrs.pdf
%% \newtheorem{prop}[thm]{Proposition}
%% \theoremstyle{plain}%default
%% \newtheorem{theorem}{Theorem}[section]
%% \newtheorem{lemma}{Lemma}[section]
%% \newtheorem{corollary}{Corollary}[section]
%% \newtheorem{definition}{Definition}[section]
%% \newtheorem{remark}{Remark}[section]
%% \newtheorem{example}{Example}[section]
%% \newtheorem{exercise}{Exercise}[section]
\newcommand{\less}[1]{#1_{<}}
\newcommand{\pfn}{\rightharpoonup}
\newcommand{\ffn}{\stackrel{{\sf fin}}{\rightharpoonup}}
\newcommand{\stkout}[1]{\ifmmode\text{\sout{\ensuremath{#1}}}\else\sout{#1}\fi}
% Caution: Not supported by MathJax!
% ----------------------------------
% \DeclareMathSymbol{\shortminus}{\mathbin}{AMSa}{"39}
% \usepackage{amsfonts} %% <- also included by amssymb
% \DeclareMathSymbol{\shortminus}{\mathbin}{AMSa}{"39}
\usepackage{mathpazo} %% <- because the OP uses mathpazo, optional
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\rel}{\twoheadrightarrow}
\newcommand{\map}{\rightarrow}
%\newcommand{\fixed}{\boldsymbol{\circlearrowleft}}
\newcommand{\terminal}{\not\xto{}{}}
\newcommand{\fixed}{\bm\circlearrowleft}
\newcommand{\imp}{\rightarrow}
\newcommand{\dimp}{\leftrightarrow} % double implication
\newcommand{\lequiv}{\Longleftrightarrow} % logical equivalence
\newcommand{\limplies}{\Rightarrow}
\newcommand{\lxor}{\veebar}
1 Introduction
In anticipation of the Javascript model, we refine our basic model of
objects in Scheme. The main refinement is the definition of a new
primitive to define objects, called make-basic-object which provides
a more flexible way of creating objects.
2 Immutable fields
In the refined object model, certain fields are immutable. The set of immutable fields is fixed.
immutable-field? determines which fields are immutable. In the
present implementation they are owns?, which determines whether a
field is owned by an object, and closure which is a field in
Javascript function objects.
;;; immutable-field? : symbol? -> boolean?
(define (immutable-field? x)
(memq x '(owns? closure)))
3 Identifying objects as procedures
Objects are represented as procedures.
(define obj? procedure?)
4 Error object
error-obj raises an error in response to any message it receives.
(define error-obj
(lambda (msg . args)
(error 'error-obj "no field ~a" msg)))
5 Setters, Getters and Checkers
The fundamental data structure underlying an object is a hashtable (or an environment whose entities are mutable).
The three functions below implement basic operations on a hash-table functions for a hash-table:
(define (make-setter h)
(lambda (x v)
(hash-set! h x v)))
(define (make-getter h parent)
(lambda (x)
(hash-ref h x (lambda () (parent x)))))
(define (make-checker h)
(lambda (x)
(hash-has-key? h x)))
6 The basic-make-obj function
Let o be an object. The parent of o is an object p consulted
during the lookup of a field f not owned by o.
The basic-make-obj function takes a parent, and hash table binds
that holds bindings, and a thunk init. It builds a simple object
with a message interface, populates the object with an owns? method,
and then further initialises the object with init before returning
it.
The main difference between the earlier make-obj and
basic-make-obj is presence of a hash table as a parameter. This is
necessary so that certain updates on the hash table may happen from
within, e.g., during the installation of the closure and owns?
fields. (See the implementations of make-obj based on
basic-make-obj in the next section.)
(define basic-make-obj
(lambda (parent binds init)
(let ([set (make-setter binds)]
[get (make-getter binds parent)]
[chk (make-checker binds)])
(let ([o
(lambda msg
(match msg
[(list (? symbol? x)) (get x)]
[(list (? symbol? x) v)
(if (immutable-field? x)
(error 'make-obj "field not mutable ~a" x)
(set x v))]
[else (error 'make-obj
"invalid object lookup syntax ~a" msg)]))])
(let ([owns? (lambda (this x) (chk x))])
(set 'owns? owns?)
(init)
o)))))
7 Constructing objects using make-obj
make-obj creates an object with a parent. The default parent is
error-obj. An object with error-obj as parent is called a
ground object.
(define (select/default thing default)
(if (null? thing)
default
(first thing)))
(define make-obj
(lambda parent ;; '() or a singleton list.
(let ([parent (select/default parent error-obj)])
(let ([binds (make-hash)])
(basic-make-obj parent binds void)))))
Note that void is the Scheme function that takes nothing and returns
nothing.
8 Method calls
We have learned earlier that a method is a function that takes an
object and additional arguments. A method may be installed as a field
of an object. A method call with name method-name in the context
of an object a first locates method against method-name in a.
Then it invokes method with a and any additional arguments args.
(define call
(lambda (a method-name . args)
(let ([method (a method-name)])
(apply method (cons a args)))))
9 Literal objects
obj takes a list of bindings and builds a ground object:
(define obj
(lambda binds
(let ([a (make-obj)])
(for-each (lambda (bind)
(a (first bind) (second bind)))
binds)
a)))
10 Unit tests
(require rackunit)
(require rackunit/text-ui)
(define (check-err thunk)
(check-exn exn:fail? thunk))
(define check-eq check-eq?)
(define literal-tc
(test-case
"literals and owns?"
(let ()
(define a (obj '(x 3)))
(define b (make-obj a))
(check-eq (a 'x) 3)
(check-err (lambda () (a 'y)))
(check-true (call a 'owns? 'x))
(check-false (call a 'owns? 'y))
(b 'y 5)
(check-eq (b 'y) 5)
(check-eq (b 'x) 3)
(check-false (call b 'owns? 'x))
;;; error trying to set owns? field
(check-err (lambda () (b 'owns? 9)))
(check-err (lambda () (b 'closure 0)))
)))
11 Source code
- ./obj.rkt
- Implementation of Scheme objects using the
basic-make-objmechanism.