2021-06-05 - Chaos: The Last Question

I am investigating this pattern combinator thing, because pattern are everywhere in programming e.g Chomsky's grammars, and also Machine Learning. The thing I am trying to build is different from Machine Learning pattern recognition. Pattern combinators are neither supervised nor unsupervised, they do not learn, they are teached with a specification constructed with combinators (procedure + data typed by a human) how to recognize patterns.

Pattern matching facility ease the work of constructing an interpreter or compiler. They are the basis of Scheme syntax-rule, syntax-case, nanopass framework, Kernel, and GNU Guile compiler tower [GNU-GUILE]. Part of Guile compiler tower, there is foldt* by Andy Wingo. foldt* builds upon Kiselyov's foldt (from Little Schemer fame, see). Both foldt and foldt* allow to recognize patterns in s-expr, they also allow to construct a new object (just like regular fold). Pattern combinators are concerned about traversing the source; the patterns in that source are recognized with user produced procedures (fhere, fdown, fup); pattern combinators always contruct an object following the same template, that is a flat environment, such as a mapping or association list.

In the previous note, I have glossed over sum that re-surface the implementation of a procedure. dubito some kind of inference engine. cogito was barely mentioned, but I meant it as an eval.

In this note, I will try to explain how (sum cogito) works.

Here is the Shutt's Equation of Software:

(define eval
  (lambda (exp env)

    (cond
     ;; The first clause will apply (in the sense of Scheme) a
     ;; procedure or a pseudo-macro; `(kernel-car exp)` is the
     ;; operator; `(kernel-cdr exp)` is the arguments as Scheme list
     ;; of symbols.
     ((kernel-pair? exp)  (combine (eval (kernel-car exp) env)
                                   (kernel-cdr exp)
                                   env))
     ;; search the symbol called `exp` inside the environment called
     ;; `env`. It is very often that the code goes through this clause;
     ;; hence it could be useful to optimize ahead-of-time (AOT).
     ((symbol? exp)  (lookup exp env context))
          (else exp))))

This is a slightly modified version of SINK's eval, I dropped the context that is the reification of a continuation, that in (call/cc proc) is passed to PROC. Unlike in Scheme, a context is encapsulated ie. it is its own type (see Racket and Gambit).

Tentative emulation of Kernel with Scheme

About Scheme, I will try to describe the semantic of Kernel using Scheme without actually building an interpreter in Scheme (that is what SINK does). Instead, I will describe a subset of Kernel in particular, the $vau operative, that allows to create new operative with Scheme pseudo-code:

(define-syntax $vau
  (lambda (stx)
    (syntax-case stx ()
      (($vau args env body ...)
       #'(lambda (args env) body ...)))))

That is wild guess ie. prelimeray translation. To call a procedure constructed with $vau you need another syntax transformer and a few helpers:

(define-syntax apply-vau
  (lambda (stx)
    (syntax-case stx ()
      ((apply-vau operative args ...)
       #'(let ((dynamic-environment (environment-current)))
           (operative 'args dynamic-environment))))))

(Now that I think about it, it can be implemented in terms of syntax-rule)

Mind the quoted args, args is constructed in the template as a quoted expression, and its evaluation might be done in body ... with the help of Scheme's (eval exp environment).

environment-current is like Guile's the-environment.

Another emulation of Kernel with Scheme

Another approach is to use only procedures and no macros. For instance:

(define (my-operative args env)
  body ...)

Since there is two kinds of callables in Kernel: operative and applicative. One will need to prefix every Scheme call with a kernel-call:

(define (kernel-call combiner env args)
  (if (applicative? combiner)
      ((unwrap combiner) (map (lambda (arg) (eval arg env))))
      ;; otherwise, it is an operative
      (combiner args env)))

Where applicative? is the predicate associated with:

(define-record-type <applicative>
  (wrap operative)
  applicative?
  (operative unwrap))

Then what you write in Kernel as:

(my-combiner a b c)

Would be transpiled as:

(kernel-call my-combiner (environment-current) (list 'a 'b 'c))

(environment-current) can be constructed at compile time, since it is the static / lexical scope.

The only missing piece I can forsee is that Kernel support trees as operands, but that requires more work, including a procedural pattern matcher.

sum, or no sum

Previously, I wrote the goal of sum is ultimately to call (sum eval) and return an object language representation of eval in the meta-language. In other words, it would return the full source of the compiler, one language-level below the object language.

I will investigate (sum +): what is the meta-language definition of the applicative + in Scheme:

(define (sum +)
  (applicative (operative (lambda (args env) (+ (env-ref env 'a) (env-ref env 'b))))))

It does not make sense to compile a mere lambda, you need a full lambda such as:

(lambda (args env) (+ (env-ref env 'a) (env-ref env 'b)))

It would be transpiled to the following web assembly:

(func $a.683 (param $cl.397 externref) (result i32) (result externref)
      (local $a externref)
      (local $b externref)
      (local $out externref)
      (local.set $k (table.get $stack (i32.const 0)))
      (local.set $a (table.get $stack (i32.const 1)))
      (local.set $b (table.get $stack (i32.const 2)))
      (local.set $out (call $+ (local.get $a) (local.get $a)))
      (table.set $stack (i32.const 0) (local.get $out))
      (i32.const 1) ;; continue = yes
      (local.get $k)) ;; continuation closure

The previous text would be the representation of (sum (sum +)) in the object language.

References