Mutual recursion #32

New Issue

scott · 2024-05-15T23:04:03Z

scott commented

2024-05-15 23:04:03 +00:00

Tracking:

bare fn foo will parse as a forward declaration
validator will accept fn foo
validator will add a forward-declared function to ctx
validator will ensure there are no undefined forward-declared functions
interpreter will panic if a forward-declared function is called before it is defined

At current, the validator will reject mutually recursive functions.

fn foo () -> bar () & error: unbound name `bar`
fn bar () -> foo ()

First of all, do we want mutual recursion? Do we need it? Where? (For example, writing a recursive descent parser requires mutual recursion...)

In Janet, the way you do this is:

(set bar nil)
(defn foo [] (bar))
(defn- bar* [] (foo))
(set bar bar*)

In Clojure, you'd do this:

(declare bar)
(defn foo [] (bar))
(defn bar [] (foo))

The Ludus equivalent to the former is:

ref bar = nil
fn foo () -> deref (bar) ()
fn bar_  () -> foo ()
set! (bar, bar_)

A Ludus equivalent to the latter could be:

fn bar
fn foo () -> bar ()
fn bar () -> foo ()

This seems pretty straightforward to implement: parse, validate, and run. In addition, it has the added benefit of ensuring that you can only forward-declare functions. You could also easily validate that a forward-declared function is actually implemented.

It would still have to be a runtime error if you call a declared function that hasn't been defined yet.

Tracking: - [ ] bare `fn foo` will parse as a forward declaration - [ ] validator will accept `fn foo` - [ ] validator will add a forward-declared function to ctx - [ ] validator will ensure there are no undefined forward-declared functions - [ ] interpreter will panic if a forward-declared function is called before it is defined --- At current, the validator will reject mutually recursive functions. ``` fn foo () -> bar () & error: unbound name `bar` fn bar () -> foo () ``` First of all, do we want mutual recursion? Do we need it? Where? (For example, writing a recursive descent parser requires mutual recursion...) In Janet, the way you do this is: ``` (set bar nil) (defn foo [] (bar)) (defn- bar* [] (foo)) (set bar bar*) ``` In Clojure, you'd do this: ``` (declare bar) (defn foo [] (bar)) (defn bar [] (foo)) ``` The Ludus equivalent to the former is: ``` ref bar = nil fn foo () -> deref (bar) () fn bar_ () -> foo () set! (bar, bar_) ``` A Ludus equivalent to the latter could be: ``` fn bar fn foo () -> bar () fn bar () -> foo () ``` This seems pretty straightforward to implement: parse, validate, and run. In addition, it has the added benefit of ensuring that you can only forward-declare functions. You could also easily validate that a forward-declared function is actually implemented. It would still have to be a runtime error if you call a declared function that hasn't been defined yet.

scott added the

enhancement

semantics

syntax

labels 2024-05-15 23:04:03 +00:00

scott self-assigned this 2024-05-15 23:04:03 +00:00

scott commented

2024-05-16 00:10:08 +00:00

See https://rosettacode.org/wiki/Mutual_recursion#

scott added this to the 0.2.0 milestone 2024-05-19 19:52:59 +00:00

scott modified the milestone from 0.2.0 to Computer Class

2024-05-23 23:33:33 +00:00

scott commented

2024-05-23 23:34:44 +00:00

We need mutual recursion for Sierpinski triangles, which we want to do in Computer Class. Shifted milestone to recognize this.

scott commented

2024-06-04 15:56:16 +00:00

Added in bbd41a0f74

Format:

fn foo
fn bar () -> foo ()
fn foo () -> :foo
bar () & => :foo
fn baz
baz () & => panic! cannot call function before it is defined

Added in https://alea.ludus.dev/twc/ludus/commit/bbd41a0f748aa0bdde811f98a1ba230448fc4904 Format: ``` fn foo fn bar () -> foo () fn foo () -> :foo bar () & => :foo fn baz baz () & => panic! cannot call function before it is defined ```

scott closed this issue

2024-06-04 15:56:16 +00:00

Sign in to join this conversation.