Moving a Rust/Haskell abstract algebra library to Racket?

[Stuart Hungerford]

Hi Racketeers,

I'd like to try re-implementing a library for experimenting with abstract algebraic structures in Racket (that is groups, fields, rings etc, not algebraic data types like sum or product types). With Racket's strong numeric hierarchy and programmable programming language philosophy it seems like a good environment for experimenting with mathematical structures.

This library was originally developed in Rust and more recently Haskell and made heavy use of Rust traits and Haskell typeclasses to implement these structures for the builtin numeric types as a well as my own derived numeric types (e.g. finite fields). I understand Racket is not Haskell (or Rust) and naively trying to emulate typeclasses or traits in Racket will likely lead to un-idiomatic code. Having said that, what Racket idioms would be most useful for this kind of project?

A typical typeclass (from the Haskell version) would be:

```
class Monoid a => Group a where

  inverse :: a -> a

  power :: Int -> a -> a
```

Thanks,

Stu

[Robby Findler]

I'm no expert on algebras, but I think the way to work on this is not to think "what Racket constructs are close that I might coopt to express what I want?" but instead to think "what do I want my programs to look like" and then design the language from there, reusing libraries as they seem helpful or designing new ones that do what you want. Racket's language-implementation facilities are pretty powerful (of course, if there is nothing like what you end up needing, there will still be actual programming to do ;).

Robby

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/a1ce47b2-9dab-4b33-b50b-557bfef7e331n%40googlegroups.com.

[Stuart Hungerford]

On Wednesday, 20 January 2021 at 12:34:59 UTC+11 Robby Findler wrote:

I'm no expert on algebras, but I think the way to work on this is not to think "what Racket constructs are close that I might coopt to express what I want?" but instead to think "what do I want my programs to look like" and then design the language from there, reusing libraries as they seem helpful or designing new ones that do what you want. Racket's language-implementation facilities are pretty powerful (of course, if there is nothing like what you end up needing, there will still be actual programming to do ;).

Thanks Robby -- that's a very interesting way to look at library design that seems to make particular sense in the Racket environment.

Stu

[Jens Axel Søgaard]

An example of such an approach is racket-cas, a simple general purpose cas, which
represents expressions as s-expression. 

The polynomial 4x^2 + 3 is represented as '(+ 3 (* 4 (expt x 2))) internally.

The expressions are manipulated through pattern matching. Instead of
using the standard `match`, I wanted my own version `math-match`.
The idea is that `math-match` introduces the following conventions in patterns:

  prefix  x y z  will match symbols only
  prefix  r s     will match numbers only (not bigfloats)
  prefix  p q    wil match exact naturals only
  prefix 𝛼 𝛽     will match exact numbers
  prefix bool   will match booleans only

  suffix .0      will match inexact numbers only
  suffix .bf     will match bigfloats only

As an example, here is the part that implements the symbolic natural logarithm
(the assumption is that the argument u is in normalized form):

(define (Ln: u)
  (math-match u
    [1  0]                                         ; ln(1)=0
    [r. #:when (%positive? r.)  (%ln r.)]          ; here %ln is an ln that handles both reals and bigfloats
    [@e  1]                                        ; @e is the syntax matching Euler's e,  ln(e)=1
    [(Complex a b) #:when (not (equal? 0 b))       ; all complex numbers are handled here
                   (⊕ (Ln (Sqrt (⊕ (Sqr a) (Sqr b))))
                      (⊗ @i (Angle (Complex a b))))]
    [(Expt @e v) v]                                ; ln(e^v) = v
    [(Expt u α) #:when (= (%numerator (abs α)) 1)  ; ln( u^(/n) ) = 1/n ln(u)  

                (⊗ α (Ln: u))]                     
    [(⊗ u v)  (⊕ (Ln: u) (Ln: v))]                 ; ln(u*v) = ln(u) + ln(v)
    [_ `(ln ,u)]))                                 ; keep as is

Note that the match pattern (⊗ u v) matches not only products of two factors, but general products.
Matching (⊗ u v)  agains (* 2 x y z) will bind u to 2 and v to (* x y z).
This convention turned out to be very convenient.

I am happy about many aspects of racket-cas, but I wish I used structs to represent the expressions.
Thanks to the custom matcher, it ought to be possible to change the underlying representation
and still reuse most parts of the code. That's a future project.


Back to your project - what is the goal of the project?
Making something like GAP perhaps?
Do you want your users to supply types - or do you want to go a more dynamic route?

/Jens Axel

[Siddhartha Kasivajhula]

Depending on what you're trying to accomplish, you may find the relation/composition module (which I authored) to be of interest. It doesn't model algebraic structures explicitly but uses them to generalize common composition operators like + (as a group), and .. (as a monoid). It also provides derived functions like power.

If this is the kind of thing you're trying to do, also take a look at generic interfaces (used in the above library) which resemble typeclasses, and which could be used to define monoids, groups, and so on as interfaces, which particular Racket types could implement.

There's also the Algebraic Racket library which I believe uses classes and objects rather than generic interfaces, and has a lot of other algebraic goodies as far as I can tell.

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/CABefVgwbdetq%2BWBa4h6MPLt1XxnhFQSiOACPC46xsx6cVA9imQ%40mail.gmail.com.

[Stuart Hungerford]

On Thursday, 21 January 2021 at 10:22:45 UTC+11 Jens Axel Søgaard wrote:

Den ons. 20. jan. 2021 kl. 08.43 skrev Stuart Hungerford <stuart.h...@gmail.com>:

On Wednesday, 20 January 2021 at 12:34:59 UTC+11 Robby Findler wrote:

I'm no expert on algebras, but I think the way to work on this is not to think "what Racket constructs are close that I might coopt to express what I want?" but instead to think "what do I want my programs to look like" and then design the language from there, reusing libraries as they seem helpful or designing new ones that do what you want. Racket's language-implementation facilities are pretty powerful (of course, if there is nothing like what you end up needing, there will still be actual programming to do ;).

Thanks Robby -- that's a very interesting way to look at library design that seems to make particular sense in the Racket environment.

An example of such an approach is racket-cas, a simple general purpose cas, which
represents expressions as s-expression. 

The polynomial 4x^2 + 3 is represented as '(+ 3 (* 4 (expt x 2))) internally.

The expressions are manipulated through pattern matching. Instead of
using the standard `match`, I wanted my own version `math-match`.
The idea is that `math-match` introduces the following conventions in patterns:

This is also fascinating (and very useful) -- thanks.  This package illustrates the build-your-own-notation approach nicely.

[...]

> Back to your project - what is the goal of the project?

> Making something like GAP perhaps?

> Do you want your users to supply types - or do you want to go a more dynamic route?

My project is really aimed at supporting self-directed learning of concepts from abstract algebra. I was taught many years ago that to really understand something to try implementing it in a high level language. That will soon expose any hidden assumptions or misunderstandings.

An early attempt (in Rust) is at: https://gitlab.com/ornamentist/un-algebra

By using the Rust trait system (and later Haskell typeclasses) I could create structure traits/typeclasses that don't clash with the builtin numeric types or with the larger more production oriented libraries in those languages in the same general area of math.

Once I added generative testing of the structure axioms I could experiment with, e.g. finite fields and ensure all the relevant axioms and laws were (at least probabilistically) met.

Thanks again Jens.

Stu

[Stuart Hungerford]

On Thursday, 21 January 2021 at 14:49:19 UTC+11 Siddhartha Kasivajhula wrote:

Depending on what you're trying to accomplish, you may find the relation/composition module (which I authored) to be of interest. It doesn't model algebraic structures explicitly but uses them to generalize common composition operators like + (as a group), and .. (as a monoid). It also provides derived functions like power.

If this is the kind of thing you're trying to do, also take a look at generic interfaces (used in the above library) which resemble typeclasses, and which could be used to define monoids, groups, and so on as interfaces, which particular Racket types could implement.

There's also the Algebraic Racket library which I believe uses classes and objects rather than generic interfaces, and has a lot of other algebraic goodies as far as I can tell.

Thanks so much for pointing these out, there's a lot of inspiration there to draw from.

Stu

[Hendrik Boom]

You might also want to look at the implementations of category theory in Agda.
Agda is a language which unifies execution and correctness proof to some
extent.

Not that you want to implement catagory theory, but category theory is a
form of algebra, and you may find some useful ideas about syntax and
semantics there.

I attended an online seminar about this recently, but I haven't been
able to find the details again. The following links seem to refer to the
same project. (I found them looking for
category theory in agda
on duckduckgo.

The software:
https://github.com/agda/agda-categories

Documents:
Formalizing Category Theory in Agda
pdf: https://arxiv.org/pdf/2005.07059.pdf
slides: https://hustmphrrr.github.io/asset/slides/cpp21.pdf

Agda itself is also worth a look.
As well as older proof assistants like coq.

There's definitely a trand towards constructivism in foundational
mathamatics.

-- hendrik

> Stu
>
>
> --

> You received this message because you are subscribed to the Google Groups "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/b14e56eb-71ef-49f4-8e98-fea4ced6e3adn%40googlegroups.com.

[Stuart Hungerford]

On Fri, Jan 22, 2021 at 12:56 AM Hendrik Boom <hen...@topoi.pooq.com> wrote:

> [...]

>
> You might also want to look at the implementations of category theory in Agda.
> Agda is a language which unifies execution and correctness proof to some
> extent.
>
> Not that you want to implement catagory theory, but category theory is a
> form of algebra, and you may find some useful ideas about syntax and
> semantics there.
>
> I attended an online seminar about this recently, but I haven't been
> able to find the details again. The following links seem to refer to the
> same project. (I found them looking for
> category theory in agda

Thanks Hendrik -- I had forgotten that Agda (and Idris, Coq, Lean) are
also good sources of inspiration in this general area.

Stu

[Jens Axel Søgaard]

Den tor. 21. jan. 2021 kl. 05.06 skrev Stuart Hungerford <stuart.h...@gmail.com>:

On Thursday, 21 January 2021 at 10:22:45 UTC+11 Jens Axel Søgaard wrote:

 

> Back to your project - what is the goal of the project?

> Making something like GAP perhaps?

> Do you want your users to supply types - or do you want to go a more dynamic route?

My project is really aimed at supporting self-directed learning of concepts from abstract algebra. 

I was taught many years ago that to really understand something to try implementing it in a high level language. 

That will soon expose any hidden assumptions or misunderstandings.

That's a very interesting project. You are so to speak optimizing for readability.
I immediately get a vision of a SICM-like book, but for algebra instead of classical mechanics.

Racket will be a good choice, since macros give you the possibility
of experimenting with suitable, easily understood syntax.

A tricky choice is to be made: how are the concepts going to be represented
as Racket values. Normal structs does not allow multiple inheritance.

Looking at a diagram such as the one below, raises the question whether the
relationship between the various concepts are to be modelled explicitly or implicitly. 

Maybe some kind of interface for each concept is needed?

/Jens Axel

Link to SICM in case you haven't seen it already.

https://mitpress.mit.edu/books/structure-and-interpretation-classical-mechanics

Note that the authors of SICM wrote a CAS in Scheme that is used in the book.

[Stuart Hungerford]

On Mon, Jan 25, 2021 at 6:52 AM Jens Axel Søgaard <jens...@soegaard.net> wrote:

That's a very interesting project. You are so to speak optimizing for readability.
I immediately get a vision of a SICM-like book, but for algebra instead of classical mechanics.

Racket will be a good choice, since macros give you the possibility
of experimenting with suitable, easily understood syntax.

A tricky choice is to be made: how are the concepts going to be represented
as Racket values. Normal structs does not allow multiple inheritance.

Looking at a diagram such as the one below, raises the question whether the
relationship between the various concepts are to be modelled explicitly or implicitly. 

Maybe some kind of interface for each concept is needed?

Thanks for pointing those relationships out -- in the earlier Rust and Haskell libraries I used a trait or typeclass for each concept/structure. I decided to make the interfaces simpler but more repetitive by having (for example) separate traits/typeclasses for Additive, Multiplicative and "abstract" groups. That allowed (for example) the real numbers to form groups under both addition and multiplication.

I'm hoping I can do something similar with Racket generic interfaces, as the other people in this thread have kindly pointed out to me in their packages and examples.

 

Link to SICM in case you haven't seen it already.

https://mitpress.mit.edu/books/structure-and-interpretation-classical-mechanics

Note that the authors of SICM wrote a CAS in Scheme that is used in the book.

One of the benefits of reading through this (with a non-physics background) is the chance to re-examine the use of notation in mathematics and how it can transfer to a computing environment.

Thanks,

Stu

 

[Jens Axel Søgaard]

Den tor. 21. jan. 2021 kl. 05.06 skrev Stuart Hungerford <stuart.h...@gmail.com>:

My project is really aimed at supporting self-directed learning of concepts from abstract algebra. 

I was taught many years ago that to really understand something to try implementing it in a high level language. 

That will soon expose any hidden assumptions or misunderstandings.

An early attempt (in Rust) is at: https://gitlab.com/ornamentist/un-algebra

By using the Rust trait system (and later Haskell typeclasses) I could create structure traits/typeclasses that don't clash with the builtin numeric types or with the larger more production oriented libraries in those languages in the same general area of math.

Once I added generative testing of the structure axioms I could experiment with, e.g. finite fields and ensure all the relevant axioms and laws were (at least probabilistically) met.

Not knowing Rust nor traits, I have amused myself writing a very simple version of traits.
 

#lang racket
(require (for-syntax syntax/parse racket/syntax))

;;;
;;; TRAITS
;;;

; This file contains a minimal implementation of traits.
; Overview:

;    (define-trait trait (method ...)
;        A trait is defined as list of methods names.

;    (implementation trait structure body ...)
;        An implementation of a trait for a given structure types,
;        associates functions to each of the methods suitable
;        for that structure type.
;        Within body, the method names can be used.

;    (with ([id trait structure expression] ...) . body)
;        Similar to (let ([id expression] ...) . body),
;        but within the body, one can use id.method
;        to call a method.

; Expansion time helpers
(begin-for-syntax
  ; These functions produce new identifiers. The context is taken from stx.
  (define (identifier:structure-method stx s m)
    (format-id stx "~a-~a" s m))
  (define (identifier:id.method stx id m)
    (format-id #'stx "~a.~a" id m))

    ; get-methods : identifier -> list-of-identifiers
  (define (get-methods trait)
    (syntax-local-value (format-id trait "~a-methods" trait))))


; SYNTAX  (define-trait Name (name ...))
;   This declares a new trait with the name Name having the methods name ....

(define-syntax (define-trait stx)
  (syntax-parse stx
    [(_define-trait Name (id ...))
       (with-syntax ([trait-methods (format-id #'Name "~a-methods" #'Name)])
         (syntax/loc stx
           (define-syntax trait-methods (list #'id ...))))]
   
    [(_define-trait Name (super-trait ...) (id ...))
     (displayln (list 'dt stx))
     (define ids    (syntax->list #'(id ...)))
     (define supers (syntax->list #'(super-trait ...)))
     (with-syntax ([trait-methods            (format-id #'Name "~a-methods" #'Name)]
                   [((super-method ...) ...) (map get-methods supers)])
       (syntax/loc stx
         (define-syntax trait-methods
           (list #'id ...
                 #'super-method ... ...))))]))



; SYNTAX  (implementation trait structure . body)
;   Defines structure-method for each method of the trait.
;   The structure-method  is bound to  method.
;   If method is defined in body, then that binding is used.
;   If method is not bound in body, but bound outside, the outside binding is used.
;   If method is not bound at all, an error is signaled.
(define-syntax (implementation stx)
  (syntax-parse stx
    [(_implementation trait structure body ...)
     (define methods (get-methods #'trait))
     (with-syntax*      
       ([(method ...)                        ; These short names are used by the user
         (for/list ([method methods])
           (syntax-local-introduce
            (format-id #'stx "~a" method)))]

        [(structure-method ...)               ; Used in the output of the `with` form.
         (for/list ([method methods])
           (identifier:structure-method #'trait #'structure method))])
       
       (syntax/loc stx
         (define-values (structure-method ...)
           (let ()
             body ...
             (values method ...)))))]))

(define-syntax (with stx)
  (syntax-parse stx
    [(_with ([id trait structure expression] ...) . body)
     (define traits         (syntax->list #'(trait ...)))
     (define ids            (syntax->list #'(id ...)))
     (define structures     (syntax->list #'(structure ...)))
     (define methodss       (map get-methods traits))

     (define (map-methods f id t s ms)
       (for/list ([m ms])
         (f id t s m)))
     
     (define (map-clauses f)
       (for/list ([id ids] [t traits] [s structures] [ms methodss])
         (map-methods f id t s ms)))
     
     (with-syntax      
       ([((id.method ...) ...)        ; names used inside `with`
         (map-clauses (λ (id t s m)
                        (syntax-local-introduce
                         (identifier:id.method #'stx id m))))]
       
        [((structure-method ...) ...) ; names used outside `with`
         (map-clauses (λ (id t s m)
                        (syntax-local-introduce
                         (identifier:structure-method t s m))))]
       
        [((it ...) ...)               ; all id (in the right shape)
         (map-clauses (λ (id t s m) id))])
     (syntax/loc stx
       (let* ([id expression] ...)
         (let-syntaxes
             ([(id.method ...) ; we need a macro in other to pass id
               (values         ; to the associated structure-method
                (λ (call-stx)  
                  (syntax-parse call-stx
                    [(_ . args)
                     (syntax/loc call-stx
                       (structure-method it . args))]))
                ...)]
              ...)
           . body))))]))

;;;
;;; Test
;;;

; Let's test the traits with a silly fish example.

(struct herring (size color) #:transparent)

(define-trait Fish (grow swim shrink))

(define (shrink f)
  (displayln (~a "This type of fish can't swim: " f)))

(implementation Fish herring
  ; swim : herring -> void
  (define (swim h)
     (match h
       [(herring s c) (displayln (~a "A " c " herring swims."))]))

  ; grow : fish integer -> fist
  ; Add the amount a to the size of of the fish.
  (define (grow h a)
    (match h
      [(herring s c) (herring (+ s a) c)])))


(define a-herring (herring 2 "gray"))

(with ([h Fish herring a-herring])
  (h.shrink)  ; picks up default definition
  (h.grow 3)) ; uses the herring implementation of Fish

;; ; =>
(let ([h a-herring])
  (herring-shrink h)
  (herring-grow h 3))

;;;
;;; A simple implementation of rings using traits.
;;;

(define-trait Set             (member? size)) ; a Set has the methods  member? and size
(define-trait Monoid (Set)    ($))            ; a Monoid is a Set    with an operation $
(define-trait Group  (Monoid) (inv))          ; a Group  is a Monoid with an operation inv
(define-trait Ring   (Group)  (+ |0| * |1|))  ; a Ring is an additive Group with an multiplicative monoid


(require (prefix-in + (only-in racket/base +))  ; ++ is now standard +
         (prefix-in * (only-in racket/base *))) ; ** is now standard *

(struct Z ())

(implementation Ring Z
   (define (member? R x) (integer? x))
   (define (size R)      +inf.0)
   ; Ring
   (define (+ R a b)     (++ a b))
   (define (* R a b)     (** a b))
   (define |0|            0)
   (define |1|            1)
   ; Group
   (define (inv R a)     (- a))
   ; Additive Monoid
   (define $ +))

(struct Zn (n))

(implementation Ring Zn
   (define (modulus R)    (Zn-n R))
   ; Set
   (define (member? R x)  (and (integer? x) (<= x (modulus R))))
   (define (size R)       (modulus R))
   ; Ring
   (define (+ R a b)      (modulo (++ a b) (modulus R)))
   (define (* R a b)      (modulo (** a b) (modulus R)))
   (define |0|            0)
   (define |1|            1)
   ; Group
   (define (inv R a)      (modulo (- a) (modulus R)))
   ; Additive Monoid
   (define $ +))


(struct Zx (x p))   ; p(x) belongs to Z[x], the ring of polynomials over Z

(require (prefix-in cas: racket-cas))

(implementation Ring Zx
   (define (var R)        (Zx-x R))
   ; Set
   (define (member? R f)  (cas:polynomial? f (var R))) ; approximate
   (define (size R)       +inf.0)
   ; Ring
   ;   Note: We are assuming a and b are normalized.
   ;         If a and b are normalized, the return values from + and * will
   ;         automatically be normalized.
   (define (+ R a b)      (cas:plus a b))                
   (define (* R a b)      (cas:expand (cas:times a b)))
   (define |0|            0)
   (define |1|            1)
   ; Group
   (define (inv R a)      (cas:times -1 a))
   ; Additive Monoid
   (define $ +))


(struct Zx/I (x I)) ; the ideal I is represented by a polynomial p
; The ring of single variable polynomials over Z modulo an ideal I.
; Note: We are using racket-cas to compute, and it supports polynomials
;       over Z, Q and floating points. It does support polynomials
;       in several variables, so Zxy/I can be implemented in the same
;       manner.
(implementation Ring Zx/I
   (define (var R)        (Zx/I-x R))
   (define (I R)          (Zx/I-I R)) ; a polynomial
   (define (inject R p)   (cas:polynomial-remainder p (I R) (var R)))
   ; Set
   (define (member? R f)  (cas:polynomial? f (var R))) ; approximate
   (define (size R)       +inf.0)
   ; Ring
   (define (+ R a b)      (inject R (cas:plus a b)))
   (define (* R a b)      (inject R (cas:expand (cas:times a b))))
   (define |0|            0)
   (define |1|            1)
   ; Group
   (define (inv R a)      (cas:times -1 a))
   ; Additive Monoid
   (define $ +))



(with ([R Ring Z (Z)])
 (R.* (R.+ 1 2) 3))     ; => 9

(with ([R Ring Zn (Zn 5)])
 (R.* (R.+ 1 2) 3))    ; => 4

(with ([R Ring Zx Zx])
  (R.* (R.+ 'x 1) (R.+ 'x 1)))

(with ([R Ring Zx/I (Zx/I 'x (cas:normalize '(+ (* x x) 1)))])
  (R.* 'x 'x))  ; => -1

(with ([R Ring Zx/I (Zx/I 'x (cas:normalize '(+ (* x x) 1)))])
  (R.* (R.+ 'x 1) (R.+ 'x 1))) ; => 2x

[Stuart Hungerford]

On Sunday, 31 January 2021 at 08:07:27 UTC+11 Jens Axel Søgaard wrote:

Den tor. 21. jan. 2021 kl. 05.06 skrev Stuart Hungerford <stuart.h...@gmail.com>:

[...]

By using the Rust trait system (and later Haskell typeclasses) I could create structure traits/typeclasses that don't clash with the builtin numeric types or with the larger more production oriented libraries in those languages in the same general area of math.

Once I added generative testing of the structure axioms I could experiment with, e.g. finite fields and ensure all the relevant axioms and laws were (at least probabilistically) met.

Not knowing Rust nor traits, I have amused myself writing a very simple version of traits.
 

#lang racket
(require (for-syntax syntax/parse racket/syntax))

;;;
;;; TRAITS
;;;

Many thanks Jens.  This is an excellent example of Racket's build-your-own-abstractions philosophy at work.  (Although where I live I would have used bream or sharks instead of herring ;-)

If Hackett was still maintained I would probably use it too.

Thanks,

Stu