Add basic support for recur

[issadarkthing]

Hi guys, I've added a basic support for recur which will optimize function to create tail-call optimization.

package main

import (
    "fmt"
    "time"

    "github.com/spy16/sabre"
)

const rangeTco = `
(def range (fn* range [min max coll]
                 (if (= min max)
                   coll
                   (recur (inc min) max (coll.Conj min)))))

(print (range 0 10 '()))
(range 0 1000 '())
`

const rangeNotTco = `
(def range (fn* range [min max coll]
                 (if (= min max)
                   coll
                   (range (inc min) max (coll.Conj min)))))

(print (range 0 10 '()))
(range 0 1000 '())
`

func main() {
    scope := sabre.New()
    scope.BindGo("inc", inc)
    scope.BindGo("print", fmt.Println)
    scope.BindGo("=", sabre.Compare)

    initial := time.Now()
    _, err := sabre.ReadEvalStr(scope, rangeNotTco)
    if err != nil {
        panic(err)
    }
    final := time.Since(initial)
    fmt.Printf("no recur: %s\n", final)

    initial = time.Now()
    _, err = sabre.ReadEvalStr(scope, rangeTco)
    if err != nil {
        panic(err)
    }
    final = time.Since(initial)
    fmt.Printf("recur: %s\n", final)
}

func inc(val sabre.Int64) sabre.Int64 {
    return val + 1
}

result:

$ go run main.go
(0 1 2 3 4 5 6 7 8 9)
no recur: 319.056393ms
(0 1 2 3 4 5 6 7 8 9)
recur: 14.510449ms

[spy16]

That's brilliant! 🔥. Thanks a lot for your contribution. Let me take a look at the PR sometime today/tomorrow, and get back to you.

(Note: Due to some limitations in Sabre and certain optimisations we could do, we are redesigning it from scratch under parens. You're welcome to contribute 🙂 )

[lthibault]

@issadarkthing Thanks for your contribution!

Out of curiosity, what are you using Sabre for?

Also, I really hope you'll come join us over at https://github.com/spy16/parens. The switch should be pretty seamless, but please let me know if you hit any issues when migrating.

[issadarkthing]

I am using it to create a custom DSL for TUI application using tview library. The repo is here https://github.com/issadarkthing/xlisp; for now Im still experimenting with the language itself.