Trampolining example using Free

[lostintime]

Hello,

I'm trying to run a basic trampolined recursive function, but stack gets blown anyway,

What I'm doing wrong and how can I do it right ?

Here is my code (typescript, monet v0.8.10):

import {Free} from 'monet';

function extract<T>(f: () => T):T  {
  return f();
}

function sumT(n: number): Free<number> {
  if (n == 0) {
    return Free.Return(0)
  }

  return Free.Suspend<number, () => Free<number>>(
    () => sumT(n - 1).flatMap((r) => Free.Return(r + n))
  )
}

console.log('sum', sumT(100000).go(extract));

And this is the result:

./node_modules/monet/src/main/javascript/monet.js:930
    Function.prototype.andThen = Function.prototype.map = function (g) {
                                                                   ^

RangeError: Maximum call stack size exceeded
    at Function.andThen.Function.map (./node_modules/monet/src/main/javascript/monet.js:930:68)
    at Object.bind (./node_modules/monet/src/main/javascript/monet.js:828:34)
    at monet_1.Free.Suspend (./dist/test.js:10:51)
    at ./node_modules/monet/src/main/javascript/monet.js:933:22
    at ./node_modules/monet/src/main/javascript/monet.js:933:22
    at ./node_modules/monet/src/main/javascript/monet.js:933:22
    at ./node_modules/monet/src/main/javascript/monet.js:933:22
    at ./node_modules/monet/src/main/javascript/monet.js:933:22
    at ./node_modules/monet/src/main/javascript/monet.js:933:22
    at ./node_modules/monet/src/main/javascript/monet.js:933:22

Process finished with exit code 1

For the reference - tried the same with scala and cats:

import cats.Functor
import cats.free.Trampoline
import cats.free.Trampoline._

/**
  * recursive sum, no tailrec, let it blow
  */
def sumR(n: Int): Int = {
  if (n <= 0) {
    0
  } else {
    n + sumR(n - 1)
  }
}

/**
  * Trampolined sum
  * type Trampoline[A] = Free[Function0, A]
  */
def sumT(n: Int): Trampoline[Int] = {
  if (n <= 0) {
    done(0)
  } else {
    suspend {
      sumT(n - 1)
        .flatMap(r ⇒ {
          done(r + n)
        })
    }
  }
}

implicit val fn = new Functor[Function0] {
  override def map[A, B](fa: () ⇒ A)(f: (A) ⇒ B): () ⇒ B = () ⇒ f(fa())
}

val xT: Int = sumT(100000).go(f ⇒ f())
println(s"xT: $xT")
val xR: Int = sumR(100000)
println(s"xR: $xR")

sumT works fine, sumR fails with java.lang.StackOverflowError

Thanks in advance ).

[cwmyers]

I can't see what's wrong with your example. It is very similar to what we have in the tests:

https://github.com/cwmyers/monet.js/blob/master/test/free-spec.js#L41-L55

Have you tried simple running .run instead of .go?

Thanks for your message.

[lostintime]

Hello and thanks for quick reply

Tried with .run() - same issue there.

The difference with the test - is flatMap used inside suspend() function, without that transformation it works fine, stack is safe but it becomes useless. It may be the closure from flatMap which catches outer context, but I didn't dive to deep into.

[sudo97]

My intuition tells me that this is not a tail call, when you use flatMap, it's not sumT that performed the last, you kinda do something with result of sumT after you called it in order for it to be TCO it should be:
function sumT(n: number, acc = 0): Free<number> {
return n === 0
? Free.Return(acc)
: Free.Suspend<number, () => Free<number>>(() => sumT(n - 1, acc + n));
}

[Laylow187]

./node_modules/monet/src/main/javascript/monet.js:930
Function.prototype.andThen = Function.prototype.map = function (g) {
^

RangeError: Maximum call stack size exceeded
at Function.andThen.Function.map (./node_modules/monet/src/main/javascript/monet.js:930:68)
at Object.bind (./node_modules/monet/src/main/javascript/monet.js:828:34)
at monet_1.Free.Suspend (./dist/test.js:10:51)
at ./node_modules/monet/src/main/javascript/monet.js:933:22
at ./node_modules/monet/src/main/javascript/monet.js:933:22
at ./node_modules/monet/src/main/javascript/monet.js:933:22
at ./node_modules/monet/src/main/javascript/monet.js:933:22
at ./node_modules/monet/src/main/javascript/monet.js:933:22
at ./node_modules/monet/src/main/javascript/monet.js:933:22
at ./node_modules/monet/src/main/javascript/monet.js:933:22

Process finished with exit code 1
import {Free} from 'monet';

function extract(f: () => T):T {
return f();
}

function sumT(n: number): Free {
if (n == 0) {
return Free.Return(0)
}

return Free.Suspend<number, () => Free>(
() => sumT(n - 1).flatMap((r) => Free.Return(r + n))
)
}

console.log('sum', sumT(100000).go(extract));

[Laylow187]

Overview and Purpose

Millions of developers across the world host millions of projects—both open and closed source—on GitHub. We're fortunate to be able to play a part in enabling collaboration across the developer community every day, which is a responsibility we don’t take lightly. Together, we all have the exciting opportunity to make this a community we can be proud of.

GitHub Community, powered by GitHub Discussions, is intended to be a place for further collaboration, support, and brainstorming. This is a civilized place for connecting with other users, learning new skills, sharing feedback and ideas, and finding all the support you need for your GitHub projects. By participating in GitHub Community, you are agreeing to the same Terms of Service and GitHub Acceptable Use Policies that apply to GitHub.com, as well as this GitHub Community-specific Code of Conduct.

With this Code of Conduct, we hope to help you understand how best to collaborate in GitHub Community, what you can expect from moderators, and what type of actions or content may result in temporary or permanent suspension from community participation. We will investigate any abuse reports and may moderate public content within GitHub Community that we determine to be in violation of either the GitHub Terms of Service or this Code of Conduct.

Our diverse user base brings different perspectives, ideas, and experiences, and ranges from people who created their first "Hello World" project last week to the most well-known software developers in the world. We are committed to making GitHub an environment that welcomes all the different voices and perspectives our community has to offer, while maintaining a safe place for developers to do their best work.

Pledge

In the interest of fostering an open and welcoming environment, we as contributors and maintainers pledge to making participation in GitHub Community a harassment-free experience for everyone, regardless of age, body size, disability, ethnicity, gender identity and expression, level of experience, nationality, personal appearance, race, religion, or sexual identity and orientation.

Standards

Treat GitHub Community with respect. We are a shared resource — a place to share skills, knowledge, and interests through ongoing conversation.

The following are not hard and fast rules, merely aids to the human judgment of our community. Use these guidelines to keep this a clean, well-lighted place for civilized public discourse.

Best Practices for Maintaining a Strong Community

The primary purpose of the GitHub community is to collaborate on software projects. We are committed to maintaining a community where users are free to express themselves and challenge one another's ideas, both technical and otherwise. At the same time, it's important that users remain respectful and allow space for others to contribute openly. In order to foster both a safe and productive environment, we encourage our community members to look to these guidelines to inform how they interact on our platform. Below, you’ll find some suggestions for how to have successful interactions as a valued member of the GitHub community.

• Engage with consideration and respect.

  • Be welcoming and open-minded - New users join our community each day. Some are well-established developers, while others are just beginning. Be open to other ideas and experience levels. Make room for opinions other than your own and be welcoming to new collaborators and those just getting started.

  • Be respectful - Working in a collaborative environment means disagreements may happen. But remember to criticize ideas, not people. Share thoughtful, constructive criticism and be courteous to those you interact with. If you’re unable to engage respectfully, consider taking a step back or using some of our moderation tools to deescalate a tense situation.

  • Be empathetic - GitHub is a global community with people from a wide variety of backgrounds and perspectives, many of which may not be your own. Try to put yourself in others’ shoes and understand their feelings before you address them. Do your best to help make GitHub a community where others feel safe to make contributions, participate in discussions, and share different ideas.

• Contribute in a positive and constructive way.

  • Improve the discussion. Help us make this a great place for discussion by always working to improve the discussion in some way, however small. If you are not sure your post adds to the conversation, think over what you want to say and try again later.

    The topics discussed here matter to us, and we want you to act as if they matter to you, too. Be respectful of the topics and the people discussing them, even if you disagree with some of what is being said.

  • Be clear and stay on topic. GitHub Community is for collaboration, sharing ideas, and helping each other get stuff done. Off-topic comments are a distraction (sometimes welcome, but usually not) from getting work done and being productive. Staying on topic helps produce positive and productive discussions.

    This applies to sharing links, as well. Any links shared in GitHub Community discussions should be shared with the intent of providing relevant and appropriate information. Links should not be posted to simply drive traffic or attention to a site. Links should always be accompanied by a full explanation of the content and purpose of the link. Posting links, especially unsolicited ones, without relevant and valuable context can come across as advertising or serving even more malicious purposes.

  • Share mindfully. When asking others to give you feedback or collaborate on a project, only share valuable and relevant resources to provide context. Don't post links that don't add value to the discussion, and don't post unsolicited links to your own projects or sites on other user's threads.

    Additionally, don't share sensitive information. This includes your own email address. We don't allow the sharing of such information in GitHub Community, as it can create security and privacy risks for the poster, as well as other users. If you'd like to invite other GitHub users to collaborate on a project or work with you, share a link to the repository in which the project you are working on exists. By sharing the link to your project repo - with some information on what your project is and what kind of help or feedback you're looking for - you can invite others to collaborate with you via issues or pull requests without having to share your private information. You can also add others as outside collaborators on your project repo to give them special permissions to help you develop your project.

  • Keep it tidy. Make the effort to put things in the right place, so that we can spend more time discussing and less time cleaning up. So:

    • Don’t start a discussion in the wrong category.
    • Don’t cross-post the same thing in multiple discussions.
    • Don’t post no-content replies.
    • Don't "bump" posts, unless you have new and relevant information to share.
    • Don’t divert a discussion by changing it midstream.

    Rather than posting “+1” or “Agreed”, use the upvote button. Rather than taking an existing discussion in a radically different direction, open a new discussion.

• Be trustworthy.

  • Always be honest. Don’t knowingly share incorrect information or intentionally mislead other GitHub Community participants. If you don’t know the answer to someone’s question but still want to help, you can try helping them research or find resources instead. GitHub staff will also be active in GitHub Community, so if you’re unsure of an answer, it’s likely a moderator will be able to help.

What is not Allowed

GitHub's Acceptable Use Policies, which are part of GitHub's Terms of Service, set a baseline for what is not allowed on GitHub. Since GitHub Community is on GitHub.com, these terms and restrictions apply to GitHub Community, including the following restrictions:

• Anyone under the age of 13. If you're a child under the age of 13, you may not have an account on GitHub. GitHub does not knowingly collect information from or direct any of our content specifically to children under 13. If we learn or have reason to suspect that you are a user who is under the age of 13, we will unfortunately have to close your GitHub.com account. We don't want to discourage you from learning to code, but those are the rules. Please see our Terms of Service for information about account termination.

• Creating new account after account restriction. GitHub's Terms of Service state that "One person or legal entity may maintain no more than one free Account." Additional free accounts created to inquire about flagged or suspended accounts in GitHub will be removed.

• Other conduct which could reasonably be considered inappropriate in a professional setting. GitHub Community is a professional space and should be treated as such.

• Violation of Terms of Service. If your GitHub.com account is identified in violation of Terms of Service we will have to close your account.

Reasonable use of AI generated content

We love experimenting with new technologies, and we are especially fond of GitHub Copilot. But as with all new technology, many of us are still getting accustomed to using generative AI tools the most effectively. Here are important guidelines to follow when using generative AI to answer questions in the community:

• Take personal responsibility for everything you post.
• Read and revise the content before you post it; use your own authentic voice.
• Use your expertise as a developer to verify that the answer works and makes sense.
• Do not just post AI-generated content verbatim to inflate your reputation or give a false impression of product expertise.
• AI tools will often answer in an authoritative tone that sounds like a tech support professional. Be careful not to mislead other users into thinking that this authoritative tone means they are receiving an official response from GitHub.

Additionally, all of the guidelines listed in the previous section (Best Practices for Maintaining a Strong Community) also apply here.

The community is here for users to build trust through authentic reputations. Not adhering to these guidelines may, in some cases, constitute a Code of Conduct violation. Refer to the enforcement section below for more information.

Enforcement

What GitHub Community Participants Can Do

• If you see a problem, report it. Moderators have special authority; they are responsible for this GitHub Community. But so are you. With your help, moderators can be community facilitators, not just janitors or police.

  When you see bad behavior, don’t reply. It encourages the bad behavior by acknowledging it, consumes your energy, and wastes everyone’s time. You can report a disruptive user or disruptive content to GitHub. For more information, see "AUTOTITLE."

Our Responsibilities

There are a variety of actions that we may take in response to inappropriate behavior or content. It usually depends on the exact circumstances of a particular case. We recognize that sometimes people may say or do inappropriate things for any number of reasons. Perhaps they did not realize how their words would be perceived. Or maybe they just let their emotions get the best of them. Of course, sometimes, there are folks who just want to spam or cause trouble.

Each case requires a different approach, and we try to tailor our response to meet the needs of the situation. We'll review each situation on a case-by-case basis. In each case, we will have a diverse team investigate the content and surrounding facts and respond as appropriate, using this Code of Conduct to guide our decision.

Actions we may take in response to a flag or abuse report include, but are not limited to:

• Content Removal
• Content Blocking
• GitHub Account Suspension
• GitHub Account Termination

GitHub Community moderators who do not follow or enforce the Code of Conduct in good faith may face temporary or permanent repercussions as determined by other members of the GitHub Community's leadership.

Contacting GitHub Staff

If, for any reason, you want to contact GitHub Staff, the Community Managers, Administrators, or Moderators of GitHub Community privately, you can use our Support contact form. Contacting any member of GitHub Staff via unsolicited mentions or pings, or via channels other than GitHub Community itself, or the Support contact form is strongly discouraged and may be considered a violation of our prohibition against harassment.

Let's work together to keep GitHub Community a place where people feel safe to participate by being respectful of them and their time.

Legal Notices

Yes, legalese is boring, but we must protect ourselves – and by extension, you and your data – against unfriendly folks. We have a Terms of Service, which includes our Acceptable Use Policies, and our Privacy Statement describing your (and our) behavior and rights related to content, privacy, and laws. To use this service, you must agree to abide by our Terms of Service, GitHub Acceptable Use Policies and the Privacy Statement.

This Code of Conduct does not modify our Terms of Service—which includes our Acceptable Use Policies—and is not intended to be a complete list. GitHub retains full discretion under the Terms of Service to remove or restrict any content or accounts for activity that violates those policies, including because it is unlawful, offensive, threatening, libelous, defamatory, pornographic, obscene or otherwise objectionable, or violates any party's intellectual property or our Terms of Service. This Code of Conduct describes when we will exercise that discretion.

Data Retention and Deletion of Data

If you're a GitHub user, you may access, update, alter, or delete your basic user profile information by editing your user profile or contacting GitHub Support. We will retain and use your information as necessary to comply with our legal obligations, resolve disputes, and enforce our agreements, but barring legal requirements, will delete your full profile (within reason) within 90 days of your request. For more information please see the GitHub Privacy Statement.