search

monet / monet.js

monet.js - Monadic types library for JavaScript
https://monet.github.io/monet.js/
MIT License
1.59k stars 114 forks source link

Trampolining example using Free #104

Open lostintime opened 7 years ago

lostintime commented 7 years ago

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 commented 7 years ago

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 commented 7 years ago

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 commented 2 years ago

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 commented 6 months ago

./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 commented 6 months ago

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.

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:

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:

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

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:

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.