Is it possible to simulate FEXPRs in Racket?

[Siyuan Chen]

Dear all,

** Note that this question is not for practical programming, but just play for fun.**

I want to implement Maybe monad in Racket.

The following code works.

```
(struct Just (a)
  #:transparent)
(struct Nothing ()
  #:transparent)

(define (bigger-than-two n)
    (if (> n 2)
        (Just n)
        (Nothing)))

(define (>>= mx f)
  (match mx
    [(Nothing) (Nothing)]
    [(Just x) (f x)]))


(>>= (bigger-than-two 4)
      (λ (x)
        (>>= (bigger-than-two 5)
              (λ (y)
                (Just (+ x y))))))
```

The disadvantage of this implementation is that it doesn't look nice.

So I want to implement do notation.

One way to implement do notation is by using Lisp macro, but I don't want to use macro.

There is an alternative of Lisp macros called FEXPRs, see https://en.wikipedia.org/wiki/Macro_(computer_science)#Early_Lisp_macros

> Early Lisp macros
> Before Lisp had macros, it had so-called FEXPRs, function-like operators whose inputs were not the values computed by the arguments but rather the syntactic forms of the arguments, and whose output were values to be used in the computation. In other words, FEXPRs were implemented at the same level as EVAL, and provided a window into the meta-evaluation layer. This was generally found to be a difficult model to reason about effectively.

More information, see https://en.wikipedia.org/wiki/Fexpr

Therefore, I attempt to use fexpr to simulate macro.

The following code simulates fexpr by `eval` to implement Maybe monad.

```
(struct Just (a)
  #:transparent)
(struct Nothing ()
  #:transparent)

(define (bigger-than-two n)
    (if (> n 2)
        (Just n)
        (Nothing)))

(define (do env binds return)
  (match binds
    [nil
     (eval return env)]
    [`((,var ,e) ,rest-binds)
     (match (eval (e env))
       [(Nothing) (Nothing)]
       [(Just x) (do (extends-env env var x) rest-binds return)])]))

(do (get-current-env)
    (list '[x (bigger-than-two 4)]
          '[y (bigger-than-two 5)])
  '(Just (+ x y)))
```

Unfortunately, this code doesn't work, because it lacks two functions, `get-current-env` and `extends-env`.

Is there any way to work around this issue?

I have searched Racket's document. Racket has namespaces that are very similar to the environment here.

But it seems that `current-namespace` can not get binding (e.g. Just) and `namespace-set-variable-value!` is a mutable function which is not suitable as well.

Could someone give me some advice?
Or we can modify the code above to make it work in Racket.

Very thanks.

Best regards,

Siyuan Chen

[Hendrik Boom]

On Sun, Jun 07, 2020 at 08:09:40PM +0800, Siyuan Chen wrote:
...
...

>
> There is an alternative of Lisp macros called FEXPRs, see
> https://en.wikipedia.org/wiki/Macro_(computer_science)#Early_Lisp_macros
>
> > Early Lisp macros
> > Before Lisp had macros, it had so-called FEXPRs, function-like operators
> whose inputs were not the values computed by the arguments but rather the
> syntactic forms of the arguments, and whose output were values to be used
> in the computation. In other words, FEXPRs were implemented at the same
> level as EVAL, and provided a window into the meta-evaluation layer. This
> was generally found to be a difficult model to reason about effectively.

This wasn't just a feature for the expert user; it was the way basic
primitives like 'quote', 'cond', and 'let' were implemented in the
lisp 1.5 interpreter; the actual interpreting code being written in
assembler (or Lisp, if it wasn't an utterly necessary primitive).

-- hendrik

>
> More information, see https://en.wikipedia.org/wiki/Fexpr

...
...

[Jens Axel Søgaard]

Den søn. 7. jun. 2020 kl. 14.09 skrev Siyuan Chen <chan...@gmail.com>:

Unfortunately, this code doesn't work, because it lacks two functions, `get-current-env` and `extends-env`.

These are not available since static lexical scope makes it possible for the compiler to determine where
a variable is stored at compile time. Therefore an explicit environment is not needed.
(See "early binding" vs "late binding").
 

Is there any way to work around this issue?

 

I have searched Racket's document. Racket has namespaces that are very similar to the environment here.

But it seems that `current-namespace` can not get binding (e.g. Just) and `namespace-set-variable-value!` is a mutable function which is not suitable as well.

 

Namespaces are "environment-like" but contain only top-level variables.

Could someone give me some advice?
Or we can modify the code above to make it work in Racket.

Since this for educational/fun use and not practical, I suggest using a Scheme interpreter where the environments
are explicit.  Then you can easily add `get-current-env` and `extends-env` yourself.

One option is the interpreter page LiSP (Lisp in Small Pieces) where an interpreter for fexprs is discussed
with full working code.

/Jens Axel
https://racket-stories.com

 

[Siyuan Chen]

Hi Jens,

Thank you for telling me that Racket does not support capture and extend environments.

So that I can change direction.

Hi all,

I found that Guile has a function called `local-eval`, which can be used to simulate FEXPRs.

see https://www.gnu.org/software/guile/manual/guile.html#index-local_002deval

I implemented do-notation by `local-eval`.

```
;guile 2.2.3
(use-modules (ice-9 local-eval))
(use-modules (ice-9 match))
(use-modules (srfi srfi-9))

(define-record-type Just
  (make-Just x)
  Just?
  (x Just-x))
 
 (define-record-type Nothing
  (make-Nothing)
  Nothing?)

(define (extends-env env var-name value)
  (local-eval
   `(let ((,var-name ,value))
      (the-environment)) env))

(define (do env binds return)
  (match binds

    [()
     (begin
       (local-eval return env))]
    [((var e) rest-binds ...)
     (begin
       (match (local-eval e env)
         [($ Nothing) (make-Nothing)]
         [($ Just x) (do (extends-env env var x) rest-binds return)])
       )]))

(define (bigger-than-two n)
  (if (> n 2)

      (make-Just n)
      (make-Nothing)))

(display
 (do (the-environment)

        (list '[x (bigger-than-two 4)]
              '[y (bigger-than-two 5)])

        '(make-Just (+ x y))))
```

I was surprised that it works.

PS: The code above can be compiled and run in guile 2.2.3.

You can test it at https://rextester.com/l/scheme_online_compiler, if someone interested,

Best regards,

Siyuan Chen