% cbs-katex.sty
%
\newcommand{\STYLE}[2]{\htmlClass{cbs-#1}{#2}}
\newcommand{\DECL}[3]{\htmlId{#1:#2}{#3}}
\newcommand{\REF}[3]{\href{###1:#2}{#3}}
\newcommand{\HYPER}[5]{\href{#1/#2/index.html###3:#4}{#5}}
% \SHADE{MATH} can be defined to produce a shaded background to highlight
% inline MATH in running text:
\newcommand{\SHADE}[1]{#1}
% \KEY{TEXT}, \STRING{TEXT}, \ATOM{TEXT}, \LEX{TEXT} can be used in math mode:
\newcommand{\KEY}[1]{\textsf{\textit{\STYLE{Key}{#1}}}}
\newcommand{\STRING}[1]{\textsf{``\texttt{#1}''}}
\newcommand{\ATOM}[1]{\textsf{`\texttt{#1}'}}
\newcommand{\LEX}[1]{\textsf{\STYLE{Key}{`}\texttt{#1}\STYLE{Key}{'}}}
% The following commands produce ASCII characters that are treated specially by LaTeX:
\newcommand{\HASH}{\char`\#}
\newcommand{\DOLLAR}{\char`\$}
\newcommand{\PERCENT}{\char`\%}
\newcommand{\AMPERSAND}{\char`\&}
\newcommand{\APOSTROPHE}{\char`\'}
\newcommand{\BACKSLASH}{\char`\\}
\newcommand{\CARET}{\char`\^}
\newcommand{\UNDERSCORE}{\char`\_}
\newcommand{\GRAVE}{\char`\`}
\newcommand{\LEFTBRACE}{\char`\{}
\newcommand{\RIGHTBRACE}{\char`\}}
\newcommand{\TILDE}{\textasciitilde} % {\char`\~}
% \NAME{name} highlights the name;
% \NAMEDECL{name} declares Name.name as the target of links to name;
% \NAMEREF{name} links name to the target Name.name in the current file;
% \NAMEHYPER{url}{file}{name} links name to Name.name at url/file/file.pdf.
% Similarly for \VAR{partvariable}, \SYN{syntaxname}, \SEM{semanticsName},
% and \SECT{sectionnumber}
% The kerns in \SUB and \VAR avoid overlaps with primes:
\newcommand{\SUB}[1]{_{\kern-2mu\STYLE{PartVariable}{\textsf{#1}}}}
% PLAIN
\newcommand{\VAR}[1]{\STYLE{PartVariable}{\textsf{\textit{#1}\kern2mu}}}
\newcommand{\NAME}[1]{\STYLE{Name}{\textsf{#1}}}
\newcommand{\SYN}[1]{\STYLE{SyntaxName}{\textsf{#1}}}
\newcommand{\SEM}[1]{\STYLE{SemanticsName}{\textsf{#1}}}
\newcommand{\SECT}[1]{\STYLE{SectionNumber}{\textsf{#1}}}
% DECL
\newcommand{\VARDECL}[1]{\DECL{PartVariable}{#1}{\VAR{#1}}}
\newcommand{\NAMEDECL}[1]{\DECL{Name}{#1}{\NAME{#1}}}
\newcommand{\SYNDECL}[1]{\DECL{SyntaxName}{#1}{\SYN{#1}}}
\newcommand{\SEMDECL}[1]{\DECL{SemanticsName}{#1}{\SEM{#1}}}
\newcommand{\SECTDECL}[1]{\DECL{SectionNumber}{#1}{\textsf{#1}}}
% REF
\newcommand{\VARREF}[1]{\REF{PartVariable}{#1}{\VAR{#1}}}
\newcommand{\NAMEREF}[1]{\REF{Name}{#1}{\NAME{#1}}}
\newcommand{\SYNREF}[1]{\REF{SyntaxName}{#1}{\SYN{#1}}}
\newcommand{\SEMREF}[1]{\REF{SemanticsName}{#1}{\SEM{#1}}}
\newcommand{\SECTREF}[1]{\REF{SectionNumber}{#1}{\SECT{#1}}}
% HYPER
\newcommand{\VARHYPER}[3]{\HYPER{#1}{#2}{PartVariable}{#3}{\VAR{#3}}}
\newcommand{\NAMEHYPER}[3]{\HYPER{#1}{#2}{Name}{#3}{\NAME{#3}}}
\newcommand{\SYNHYPER}[3]{\HYPER{#1}{#2}{SyntaxName}{#3}{\SYN{#3}}}
\newcommand{\SEMHYPER}[3]{\HYPER{#1}{#2}{SemanticsName}{#3}{\SEM{#3}}}
\newcommand{\SECTHYPER}[3]{\HYPER{#1}{#2}{SectionNumber}{#3}{\SECT{#3}}}
% \LEFTPHRASE MATH \RIGHTPHRASE produces [[ MATH ]] with proper brackets:
\newcommand{\LEFTPHRASE}{\llbracket}
\newcommand{\RIGHTPHRASE}{\rrbracket}
% \LEFTGROUP MATH \RIGHTGROUP produces ( MATH ) where the parentheses are
% highlighted the same as keywords:
\newcommand{\LEFTGROUP}{\STYLE{Key}{(}}
\newcommand{\RIGHTGROUP}{\STYLE{Key}{)}}
% MATH\PLUS produces a superscript +
% MATH\STAR produces a superscript *
% MATH\QUERY produces a superscript ?
\newcommand{\PLUS}{{}^{\texttt{+}}}
\newcommand{\STAR}{{}^{\texttt{*}}}
\newcommand{\QUERY}{{}^{\texttt{?}}}
% \RULE{& PREMISE \\ & ...}{& FORMULA ... \\ & ...} produces an inference rule
% with separately aligned premises and conclusion
% PREMISE
% ...
% -----------
% FORMULA ...
% ...
\newcommand{\RULE}[2]
{\frac{\begin{aligned}#1\end{aligned}}{\begin{aligned}#2\end{aligned}}}
% \AXIOM{& FORMULA ... \\ & ...} produces an aligned formula
%
% FORMULA ...
% ...
\newcommand{\AXIOM}[1]{\begin{aligned}#1\end{aligned}}
% \TO TYPE produces => TYPE
\newcommand{\TO}{\mathop{\Rightarrow}}
% TERM \TRANS TERM produces TERM ---> TERM
\newcommand{\TRANS}{\longrightarrow}
% TERM \xrightarrow{LABEL} TERM puts the label above the long arrow
%
Unstable-Funcons-beta : Memos.cbs | PLAIN | PDF
Memos
[ Entity memo-map Funcon initialise-memos Funcon memo-value Funcon initialise-memo-value Funcon memo-value-recall ] \begin{align*}
[ \
\KEY{Entity} \quad & \NAMEREF{memo-map} \\
\KEY{Funcon} \quad & \NAMEREF{initialise-memos} \\
\KEY{Funcon} \quad & \NAMEREF{memo-value} \\
\KEY{Funcon} \quad & \NAMEREF{initialise-memo-value} \\
\KEY{Funcon} \quad & \NAMEREF{memo-value-recall}
\ ]
\end{align*} [ Entity Funcon Funcon Funcon Funcon memo-map initialise-memos memo-value initialise-memo-value memo-value-recall ]
A memo is like a mutable variable, except that the memo is updated and
accessed by a specified key, rather than by an allocated location. The
collection of memos is represented by a mutable entity that maps keys
to values.
Entity ⟨ _ , memo-map ( _ : maps ( ground-values , values ) ) ⟩ ⟶ ⟨ _ , memo-map ( _ : maps ( ground-values , values ) ) ⟩ \begin{align*}
\KEY{Entity} \quad
& \langle \_, \NAMEDECL{memo-map}(\_ : \NAMEHYPER{../../../../Funcons-beta/Values/Composite}{Maps}{maps}
( \NAMEHYPER{../../../../Funcons-beta/Values}{Value-Types}{ground-values},
\NAMEHYPER{../../../../Funcons-beta/Values}{Value-Types}{values} )) \rangle \TRANS \\&
\langle \_, \NAME{memo-map}(\_ : \NAME{maps}
( \NAME{ground-values},
\NAME{values} )) \rangle
\end{align*} Entity ⟨ _ , memo-map ( _ : maps ( ground-values , values ))⟩ ⟶ ⟨ _ , memo-map ( _ : maps ( ground-values , values ))⟩
Funcon initialise-memos ( _ : ⇒ values ) : ⇒ values Rule ⟨ initialise-memos ( X ) , memo-map ( _ ) ⟩ ⟶ ⟨ X , memo-map ( map ( ) ) ⟩ \begin{align*}
\KEY{Funcon} \quad
& \NAMEDECL{initialise-memos}(
\_ : \TO \NAMEHYPER{../../../../Funcons-beta/Values}{Value-Types}{values})
: \TO \NAMEHYPER{../../../../Funcons-beta/Values}{Value-Types}{values}
\\
\KEY{Rule} \quad
& \langle \NAMEREF{initialise-memos}
( \VAR{X} ), \NAMEREF{memo-map} ( \_ ) \rangle \TRANS
\langle \VAR{X}, \NAMEREF{memo-map} ( \NAMEHYPER{../../../../Funcons-beta/Values/Composite}{Maps}{map}
( \ ) ) \rangle
\end{align*} Funcon Rule initialise-memos ( _ : ⇒ values ) : ⇒ values ⟨ initialise-memos ( X ) , memo-map ( _ )⟩ ⟶ ⟨ X , memo-map ( map ( ))⟩
When key K \SHADE{\VAR{K}} K is associated with value V \SHADE{\VAR{V}} V , the funcon memo-value ( K , X ) \SHADE{\NAMEREF{memo-value}
( \VAR{K},
\VAR{X} )} memo-value ( K , X )
simply gives V \SHADE{\VAR{V}} V , without evaluating X \SHADE{\VAR{X}} X . When K \SHADE{\VAR{K}} K is not currently
associated with any value, it associates K \SHADE{\VAR{K}} K with the value computed
by X \SHADE{\VAR{X}} X .
Funcon memo-value ( K : ground-values , X : ⇒ values ) : ⇒ values ⇝ else ( memo-value-recall ( K ) , give ( X , sequential ( else ( initialise-memo-value ( K , given ) , null-value ) , memo-value-recall ( K ) ) ) ) \begin{align*}
\KEY{Funcon} \quad
& \NAMEDECL{memo-value}(
\VAR{K} : \NAMEHYPER{../../../../Funcons-beta/Values}{Value-Types}{ground-values}, \VAR{X} : \TO \NAMEHYPER{../../../../Funcons-beta/Values}{Value-Types}{values})
: \TO \NAMEHYPER{../../../../Funcons-beta/Values}{Value-Types}{values} \\&\quad
\leadsto \NAMEHYPER{../../../../Funcons-beta/Computations/Abnormal}{Failing}{else}
( \\&\quad\quad\quad\quad \NAMEREF{memo-value-recall}
( \VAR{K} ), \\&\quad\quad\quad\quad
\NAMEHYPER{../../../../Funcons-beta/Computations/Normal}{Giving}{give}
( \\&\quad\quad\quad\quad\quad \VAR{X}, \\&\quad\quad\quad\quad\quad
\NAMEHYPER{../../../../Funcons-beta/Computations/Normal}{Flowing}{sequential}
( \\&\quad\quad\quad\quad\quad\quad \NAMEHYPER{../../../../Funcons-beta/Computations/Abnormal}{Failing}{else}
( \NAMEREF{initialise-memo-value}
( \VAR{K},
\NAMEHYPER{../../../../Funcons-beta/Computations/Normal}{Giving}{given} ),
\NAMEHYPER{../../../../Funcons-beta/Values/Primitive}{Null}{null-value} ), \\&\quad\quad\quad\quad\quad\quad
\NAMEREF{memo-value-recall}
( \VAR{K} ) ) ) )
\end{align*} Funcon memo-value ( K : ground-values , X : ⇒ values ) : ⇒ values ⇝ else ( memo-value-recall ( K ) , give ( X , sequential ( else ( initialise-memo-value ( K , given ) , null-value ) , memo-value-recall ( K ))))
The initialisation could fail due to memoisation of a (potentially
different) value for K \SHADE{\VAR{K}} K during the computation X \SHADE{\VAR{X}} X . In that case,
the value computed by X \SHADE{\VAR{X}} X is simply discarded; a resource-safe
funcon would take an extra argument to roll back the effects of X \SHADE{\VAR{X}} X .
Funcon initialise-memo-value ( _ : ground-values , _ : values ) : ⇒ null-type Rule map-unite ( M , { K ↦ V } ) ⇝ M ′ ⟨ initialise-memo-value ( K : ground-values , V : values ) , memo-map ( M ) ⟩ ⟶ ⟨ null-value , memo-map ( M ′ ) ⟩ Rule map-unite ( M , { K ↦ V } ) ⇝ ( ) ⟨ initialise-memo-value ( K : ground-values , V : values ) , memo-map ( M ) ⟩ ⟶ ⟨ fail , memo-map ( M ) ⟩ \begin{align*}
\KEY{Funcon} \quad
& \NAMEDECL{initialise-memo-value}(
\_ : \NAMEHYPER{../../../../Funcons-beta/Values}{Value-Types}{ground-values}, \_ : \NAMEHYPER{../../../../Funcons-beta/Values}{Value-Types}{values})
: \TO \NAMEHYPER{../../../../Funcons-beta/Values/Primitive}{Null}{null-type}
\\
\KEY{Rule} \quad
& \RULE{
& \NAMEHYPER{../../../../Funcons-beta/Values/Composite}{Maps}{map-unite}
( \VAR{M},
\{ \VAR{K} \mapsto
\VAR{V} \} ) \leadsto
\VAR{M}'
}{
& \langle \NAMEREF{initialise-memo-value}
( \VAR{K} : \NAMEHYPER{../../../../Funcons-beta/Values}{Value-Types}{ground-values},
\VAR{V} : \NAMEHYPER{../../../../Funcons-beta/Values}{Value-Types}{values} ), \NAMEREF{memo-map} ( \VAR{M} ) \rangle \TRANS \\&\quad
\langle \NAMEHYPER{../../../../Funcons-beta/Values/Primitive}{Null}{null-value}, \NAMEREF{memo-map} ( \VAR{M}' ) \rangle
}
\\
\KEY{Rule} \quad
& \RULE{
& \NAMEHYPER{../../../../Funcons-beta/Values/Composite}{Maps}{map-unite}
( \VAR{M},
\{ \VAR{K} \mapsto
\VAR{V} \} ) \leadsto
( \ )
}{
& \langle \NAMEREF{initialise-memo-value}
( \VAR{K} : \NAMEHYPER{../../../../Funcons-beta/Values}{Value-Types}{ground-values},
\VAR{V} : \NAMEHYPER{../../../../Funcons-beta/Values}{Value-Types}{values} ), \NAMEREF{memo-map} ( \VAR{M} ) \rangle \TRANS \\&\quad
\langle \NAMEHYPER{../../../../Funcons-beta/Computations/Abnormal}{Failing}{fail}, \NAMEREF{memo-map} ( \VAR{M} ) \rangle
}
\end{align*} Funcon Rule Rule initialise-memo-value ( _ : ground-values , _ : values ) : ⇒ null-type ⟨ initialise-memo-value ( K : ground-values , V : values ) , memo-map ( M )⟩ ⟶ ⟨ null-value , memo-map ( M ′ )⟩ map-unite ( M , { K ↦ V }) ⇝ M ′ ⟨ initialise-memo-value ( K : ground-values , V : values ) , memo-map ( M )⟩ ⟶ ⟨ fail , memo-map ( M )⟩ map-unite ( M , { K ↦ V }) ⇝ ( )
Funcon memo-value-recall ( _ : ground-values ) : ⇒ values Rule lookup ( M , K ) ⇝ V ⟨ memo-value-recall ( K : ground-values ) , memo-map ( M ) ⟩ ⟶ ⟨ V , memo-map ( M ) ⟩ Rule lookup ( M , K ) ⇝ ( ) ⟨ memo-value-recall ( K : ground-values ) , memo-map ( M ) ⟩ ⟶ ⟨ fail , memo-map ( M ) ⟩ \begin{align*}
\KEY{Funcon} \quad
& \NAMEDECL{memo-value-recall}(
\_ : \NAMEHYPER{../../../../Funcons-beta/Values}{Value-Types}{ground-values})
: \TO \NAMEHYPER{../../../../Funcons-beta/Values}{Value-Types}{values}
\\
\KEY{Rule} \quad
& \RULE{
& \NAMEHYPER{../../../../Funcons-beta/Values/Composite}{Maps}{lookup}
( \VAR{M},
\VAR{K} ) \leadsto
\VAR{V}
}{
& \langle \NAMEREF{memo-value-recall}
( \VAR{K} : \NAMEHYPER{../../../../Funcons-beta/Values}{Value-Types}{ground-values} ), \NAMEREF{memo-map} ( \VAR{M} ) \rangle \TRANS
\langle \VAR{V}, \NAMEREF{memo-map} ( \VAR{M} ) \rangle
}
\\
\KEY{Rule} \quad
& \RULE{
& \NAMEHYPER{../../../../Funcons-beta/Values/Composite}{Maps}{lookup}
( \VAR{M},
\VAR{K} ) \leadsto
( \ )
}{
& \langle \NAMEREF{memo-value-recall}
( \VAR{K} : \NAMEHYPER{../../../../Funcons-beta/Values}{Value-Types}{ground-values} ), \NAMEREF{memo-map} ( \VAR{M} ) \rangle \TRANS
\langle \NAMEHYPER{../../../../Funcons-beta/Computations/Abnormal}{Failing}{fail}, \NAMEREF{memo-map} ( \VAR{M} ) \rangle
}
\end{align*} Funcon Rule Rule memo-value-recall ( _ : ground-values ) : ⇒ values ⟨ memo-value-recall ( K : ground-values ) , memo-map ( M )⟩ ⟶ ⟨ V , memo-map ( M )⟩ lookup ( M , K ) ⇝ V ⟨ memo-value-recall ( K : ground-values ) , memo-map ( M )⟩ ⟶ ⟨ fail , memo-map ( M )⟩ lookup ( M , K ) ⇝ ( )
←
↑