miser

The Miser Project
Applicative-Procedure λ-Abstraction 		orcmid.github.io>

miser> lambda>

index.html>
0.7.9 2026-05-27T16:32Z

In the oMiser computational model, every ob has an applicative interpretation as a script. Whether viewed as “just an ob” or as a purposive script depends on what usage is intended for it, on the context in which it is encountered.

In some cases, intention as a script is likely, since scripts have features that are unexpected in “just” obs. In essence, however, the plain/script intention is revealed only in how an ob is employed in a computation, and every ob can occur as either or both at various points in a script-driven computation.

λ-Abstraction is a systematic approach to transforming script forms into other scripts that can be applied to operands that are then used as scripts, as data, or as both. This is an important and powerful mechanism demonstrated by representations and the abstraction operations here.

1. The Abstraction Idea

Views on Abstraction
“We call the symbol λx an abstraction operator, and speak of the function which is denoted by (λx M) as obtained from the expression M by abstraction.”
– Alonzo Church [Church1941: p.7]
 
“This process [of extracting common features] can be regarded as a repeated abstraction … and under certain circumstances such abstracting processes can be repeatedly piled on top of one another. Here ‘abstract’ has to be understood in the literal meaning of the word as ‘removing’, as leaving aside everything inessential for the context in question or for a particular purpose … .”
– Hans Reichardt [VNR1977: Introduction,p.11]
 
“A high-level computer language abstracts away the machine [so that] the programmer need not be an expert in the machinations of computer hardware … in order to successfully program a computer. High-level languages (HLLs) automate, hide, or otherwise abstract away the underlying operations of the machine … .”
– Mark Jones Lorenzo [Lorenzo2019: Introduction, p.13]
 
“Abstraction is about digging deep into a situation to find out what is at its core making it tick. Another way to think of it is about stripping away irrelevant details, or rather, stripping away details that are irrelevant to what we’re thinking about.”
– Eugenia Cheng, The Joy of Abstraction [Cheng2023: 2.3 Forgetting Details]
 
“Abstraction is a verb: to abstract is to identify the basic principles and laws of a process so that it can be studied without regard to physical implementation; the abstraction can then guide many implementations. Abstraction is also a noun: An abstraction is a mental construct that unifies a set of objects. Objects of an abstraction have their own logic of relations with each other that does not require knowledge of lower-level details.”
– Peter J. Denning. Abstractions [Denning2025: What is Abstraction?]

Here, the views of Alonzo Church and Peter Denning will be favored. A view of Aristotle will also be adapted: In portrayal of abstractions there are also incidentals (sometimes called accidentals) that accompany expression and manifestation of abstractions. Incidentals are unavoidable, especially in treatment of computation. It is unfortunate whenever incidentals intrude on grasping what might be considered as the pure abstraction. Keep that in mind.

2. The Abstraction Challenge

The challenge at the oMiser/oFrugal level is the fact that there are only obs and every ob has an applicative interpretation; any ob can have an intended operational use as both data and script. The computational accomplishment of abstraction for oMiser straddles that ambiguity/flexibility of interpretation.

2.1 Pure abstraction

Pure abstraction operations on obs depend on an ob and its structure without consideration of anything other than the ob “as-is.” The result from Frugalese

σ.s M

(sigma s applied to M) is an ob such that, taken as a script applied to operand N,

(σ.s M) N

determines a form of ob M with N substituted everywhere s occurs in M. This is based strictly on ob structure and not on any interpretation of M as anything but just an ob.

Evaluation of (σ.s M) determines an ob different than M having no occurrences of s. (σ.s M) has s abstracted away (from M) in the sense expressed by Alonzo Church, quoted above. And the result is a script for an an applicative function. It is assured that

((σ.s M) s) = M as-is.

Also, if s does not occur in M, ((σ.s M) N) = M regardless of definite ob, N.

In some situations, the s in M can be though of as a variable, although there are no variables, as such, in oMiser applicative scripts. What (σ.s M) accomplishes is to effectively make s “variable” in M by abstracting it away, establishing a script that will substitute any ob for the occurrences of s in M.

This is distinct from how variables are considered in conventional programming languages and in mathematics.

2.2 Variations on that theme

The script for σ, applied to an operand ob, x, derives a new script that will abstract x from any given next operand. In the oMiser implementation of σ, operand x can be any ob, although usual practice is to use lindies (literal symbols) in the handy form σ.x. The operation comes down to matching patterns and rewriting obs to a new form that satisfies the definition of (σ.s M).

The rewriting aspect is more evident with the handy companion functions, δ(s, N) and subst(N, s):

δ(s, N) M = subst(N, s) M = (σ.s M) N = σ(s, M, N) = ((σ s) M) N

illustrating various Frugalese forms for achieving the same result, given definite s, N, and M.

The variations are convenient in different settings, including where the operands are determined and “fixed” in different applicative cases.

Keep in mind that, in oFrugal for example,

δ(s, N) M = (( δ(s) N) M)

and the intermediate forms δ(s) and ( δ(s) N) may be useful for reuse in multiple situations.

Such intermediate forms, subst(.ARG) for example, are known as curried forms. They will be employed heavily in the development of oFrugal utility scripts, including those for applicative-procedure abstraction.

2.3 The Technique

In Frugalese, σ.s M and the companion functions are expressed as follows.

 def σ.s M = if M = s
             then .arg
             else if is-individual(M)
                  then ` M
                  else if is-enclosure(M)
                       then let R = σ.s .a M
                             in if is-enclosure(R)
                                then ` M
                                else .e :: R
                       else let R = σ.s .a M,
                                S = σ.s .b M
                             in if is-enclosure(R) ∧ is-enclosure(S)
                                then ` M
                                else .c :: R :: S;

  def subst(N, s) M = (σ.s M) N;

  def δ(s, N) = subst(N, s);

An important feature of σ.s M is that the result is an enclosure (of M) when there is no occurrence of s in M. This is useful as a kind of has-no-s check, avoiding recreating portions of M that have nothing to be abstracted and made substitutable.

It is valuable that Frugalese pseudo-code is higher-level than oFrugal, providing a level of abstraction that makes the purpose and essence of the corresponding oFrugal implementation more apparent. This relies on abstraction in the senses expressed by [Lorenzo2019] and [Denning2025] (section 1, above).

The derivation of oFrugal scripts for applicative functions σ, subst, and δ is narrated in the file oSigma.

3. Symbolic Forms as Pseudocode

Symbolic forms are obs, comprised of lindies, the have the form of applicative oMiser scripts but are just that, the form without any intrinsic operational significance.

Symbolic forms are distinguished by the obaptheory predicate is-symbolic-form(x) [obaptheory: Obap3(a,b)].

When symbolic forms are evaluated as scripts for applicative expressions, the results are simply the symbolic forms themselves [obaptheory: Obap3].

For example, oFrugal expressions

alpha(x) beta(y) ` zed

and

(alpha :: x) :: (beta :: y) :: ` zed

result in the same ob canonical form (the second).

Symbolic forms can be regarded as pseudocode for applicative expressions. Transformation into an applicative-operation script is by abstracting away symbolic terms of that pseudocode.

Learning to operate with such abstraction as an operational procedure is best explored by examination of worked examples.

4. Applicative-Procedure Abstraction Heuristics

4.1 Heuristic? Hack Or Kluge?

σ.s M

The formulation of σ.s and its variations is completely functional and fully-defined (cf. 2.3). The scripts apply to the structure of operands as-is and there is no ambiguity or limitation in how those scripts provide algorithms for the claimed functions.

In contrast, by heuristics here, are meant specific computational procedures that apply under specific conditions but are not arbitrarily appropriate. There are restrictions and pitfalls that must be dealt with in choosing to apply any of the heuristics. The benefit is a “practical method that does not have to be perfect [Mulder2022].”

The proposed heuristics are not self-evident and depend on assumptions that require careful practice on the part of users. There are pitfalls that lead to unintended behavior that then has to be detected and remedied.

Risks can be mitigated by having a higher-level depiction, such as one in Frugalese, for which an oFrugal script, derived using heuristics, is shown to be functionally equivalent. (Having a Frugalese compiler would be even better, but out-of-scope for oMiser.)

For a deeper dive on heuristics and heuristic methods see [Pólya1957], [Mulder2022], and [Bensla2023].

4.2 Illustrative Cases

4.2.1 S(f, g, x) = (f x)(g x)

This important case from [combinator arithmetic: C6] can be expressed as

cS = λ.f λ.g λ.x ( (f x)(g x) )
   = λ.f λ.g λ.x ( (f :: x) :: g :: x )

where λ.s determines an applicative procedure that abstracts s from its operand, taken as a script (usually some quasi-symbolic form).

4.2.2 case(v) L

case(v) L = if is-singleton(L)
            then L
            else if (.b .a L) = v
            then .a L
            else case(v) .b L;

introduced in the Miser Project GitHub Discussion topic Handling Cases.

The operand, L, is an ob list-structure of the form

L = [r1::v1, r2::v2, …, `rx:]

and case(v) returns the first ri::vi pair for which vi = v. If there is no such pair, `rx is returned. It is the “else none-of-the-above” result. Having .a case(v) L be the result (ri) value is an oFrugal idiom for labelled forms and reporting what the determined case happens to be.

The recursive procedure is expressed in oFrugal in the form of

!def ob ^case 
     = λ.v τ.casev λ.L (.ev :: (.Q ::L :: .b :: L)
                            :: ` (    L
                                   :: ev :: (.Q :: v :: .b :: .a :: L) 
                                         :: ` (    (.a :: L) 
                                                :: casev :: .b :: L)
                                   )
                         );

The usage of τ.casev (read tau-casev or tail-casev) is a special recursion case, explained below.

4.2.3 Mirror, Mirror

The mirror function is defined mathematically by

ob.is-singleton(x) ⇒ mirror(x) = x

¬ ob.is-singleton( x ) 
     ⇒ mirror( x ) = ob.c(mirror(ob.b( x )), mirror(ob.a( x )) )

expressed computationally in Frugalese as

mirror(x) = if is-singleton(x)
            then x
            else mirror(.b x) :: mirror(.a x)

with an oFrugal implementation of the form

!def ob ^mirror
       = ρ.mirror λ.x (.ev :: (.q :: x :: .b :: x)
                           :: `(    x
                                 :: .c :: (mirror :: .b :: x)
                                       :: (mirror :: .a :: x)
                                 )
                       );

mirror just flips pairs and leaves singletons alone

In this definition, mirror flips pairs and leaves singletons alone. It has the useful verifiable property that mirror(mirror x) = x for any ob x.

4.3 The λ.x (lambda.x) Heuristic

4.4 The ρ.p (rec.p) Heuristic

4.5 The τ.p (tail.p) Heuristic

This placeholder links to raw materials and notes, including text files. There will be organized folios of content as consolidation of documentation on the web progresses.

ID Status Started Topic
sigma 0.6.1 2026-04-21 2024-05-05 σ.s M, subst(L, s), δ(s, L) definitions (authoritative)
lambda 0.5.0 2025-06-12 2024-06-20 λ.x & ρ.p Abstraction Operations (authoritative)

Using a GitHub account, discuss Miser Project topics in the Discussion section. Propose improvements and removal of defects in Miser Project documentation and software in the Issues section. There are also relevant projects from time to time. For any security concerns, please consult the project security policy.

Hard Hat Area You are navigating the Miser Project on Github

created 2024-01-25 by orcmid

This site is open source. Improve this page.