Add tail recursion optimization #29
Comments
|
This comment was originally written by mprz1024@gmail.com I think this is one of the most important features Dart is missing. Tail call elimination, or a subset of this functionality — tail recursion elimination — supports the implementation of certain algorithms in a recursive way that is easier to think for some programmers (especially those coming from mathemathical or more formal computing science background) and allows for the implementation of parts of programs without side effects, which has been proven to be less error-prone. It's a feature from many functional programming languages we would love to have in Dart. Please note that this feature hurts no one: people without the understanding of it will simply not benefit from it, but it will not make their lives harder. |
|
Removed Type-Defect label. |
|
This comment was originally written by drfibonacci@google.com Added Triaged label. |
|
Tail recursion elimination needs to be balanced against issues like debugging. There are ways to do this, and maybe at some point we will do something, but honestly, it won't be very soon, if ever. |
|
Set owner to @gbracha. |
|
Just to comment on the "this feature hurts no one". Aside from the common debug arguments there is (or can be) also a runtime cost associated with them. Tail call optimization precludes some calling-conventions (which a VM normally can chose freely). I would compare it to disallowing --fomit-frame-pointer for gcc. |
|
This comment was originally written by martin.elsman...@gmail.com I would suggest adding tail-call optimization support quickly. For programming with continuations and other advanced control operators, tail-call optimization is essential. Tail-call optimization is also necessary for programming in a functional style using tail-recursion. Finally, DART could take off quickly as a target language for compilers for functional language compilers such as Hop, SMLtoJs, AFAX, and Links, to name just a few. |
|
Let me just stress that with popular frameworks like Node.js who rely heavily on a continuation passing style, the tail call optimization does seem more than relevant. |
|
An important goal of Dart is ensuring we can generate efficient JavaScript code. |
|
This comment was originally written by LuoZhongYao...@gmail.com This is a Bug? Run retunr is false. |
|
main(){ This is not a bug. 'a' is initialized to null and (null is num) returns false. (Please file a new issue for different bug reports) |
|
Added apr30-triage label. |
|
Removed apr30-triage label. |
|
Added triage1 label. |
|
Removed this from the Later milestone. |
|
Removed Oldschool-Milestone-Later label. |
|
It is unlikely that anything will happen on this front unless JS implements it reliably on all browsers. Even then there are interesting issues. See http://gbracha.blogspot.com/2009/12/chased-by-ones-own-tail.html Added Accepted label. |
|
This comment was originally written by lessmem...@gmail.com As I understand no changes happened with this case? |
DartBot
added
Type-Enhancement
area-language
Changes: ``` > git log --format="%C(auto) %h %s" 5631a06..f594d86 https://dart.googlesource.com/clock.git/+/f594d86 Switch from homepage to repository in pubspec (#32) https://dart.googlesource.com/clock.git/+/72c709a Update CI (#30) https://dart.googlesource.com/clock.git/+/be93d8f Fix formatting (#29) ``` Diff: https://dart.googlesource.com/clock.git/+/5631a0612f4ac7e1b32f7c9a00fc7c00a41615e1~..f594d86da123015186d5680b0d0e8255c52fc162/ Change-Id: I3546bfa0c3e4bd6714467c866cfc1368c30f87bb Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/244769 Reviewed-by: Kevin Moore <kevmoo@google.com> Commit-Queue: Devon Carew <devoncarew@google.com>
Changes: ``` > git log --format="%C(auto) %h %s" 7c73ec8..3e695bc https://dart.googlesource.com/test_process.git/+/3e695bc Merge pull request #33 from dart-lang/repository_field https://dart.googlesource.com/test_process.git/+/da43a51 populate the repository field https://dart.googlesource.com/test_process.git/+/18d26e5 Bump actions/checkout from 2 to 3 (#32) https://dart.googlesource.com/test_process.git/+/5ec59cb Merge pull request #30 from scheglov/meta-1.3.0 https://dart.googlesource.com/test_process.git/+/b33c7a2 Revert to 'meta: ^1.3.0'. https://dart.googlesource.com/test_process.git/+/4c55feb Merge pull request #29 from scheglov/meta-2.0.0 https://dart.googlesource.com/test_process.git/+/6b0c025 Update 'meta' constraint to '>=1.3.0 <3.0.0'. https://dart.googlesource.com/test_process.git/+/7ac00ea Update test-package.yml (#28) https://dart.googlesource.com/test_process.git/+/653e3ba Bump dart-lang/setup-dart from 0.3 to 1 (#27) https://dart.googlesource.com/test_process.git/+/d789476 Add dependabot https://dart.googlesource.com/test_process.git/+/52732de Merge pull request #26 from dart-lang/franklinyow-patch-1 https://dart.googlesource.com/test_process.git/+/6c13ab5 Update LICENSE https://dart.googlesource.com/test_process.git/+/1c9aadb Fix formatting (#25) https://dart.googlesource.com/test_process.git/+/c7416f1 Prepare to publish (#24) ``` Diff: https://dart.googlesource.com/test_process.git/+/7c73ec8a8a6e0e63d0ec27d70c21ca4323fb5e8f~..3e695bcfeab551473ddc288970f345f30e5e1375/ Change-Id: I2bf20858f603f34a3a22bfd19653014035ff4e3c Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/245226 Reviewed-by: Kevin Moore <kevmoo@google.com> Commit-Queue: Devon Carew <devoncarew@google.com>
Changes: ``` > git log --format="%C(auto) %h %s" d80f4d0..c0c4c47 https://dart.googlesource.com/mime.git/+/c0c4c47 Add .webmanifest to extension map (#29) https://dart.googlesource.com/mime.git/+/642c9ce Improve handling for audio: aac, mp3, ogg, webm (#57) https://dart.googlesource.com/mime.git/+/a714658 Add image/heif to extension map (#52) https://dart.googlesource.com/mime.git/+/4529fa7 Add woff2 mime type (#43) https://dart.googlesource.com/mime.git/+/b5f5087 Add application/toml mimeType lookup by file path (#64) https://dart.googlesource.com/mime.git/+/dcf97ee Add `image/heic` mime type (#58) ``` Diff: https://dart.googlesource.com/mime.git/+/d80f4d09067af87d84d9cb647acfa4d2d313d795~..c0c4c47a3d7bf696f1aa1959fb83d598baadb33c/ Change-Id: I3f2a8dde66c1c2744e708999e56f5441bc389e91 Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/270220 Auto-Submit: Nate Bosch <nbosch@google.com> Commit-Queue: Nate Bosch <nbosch@google.com> Commit-Queue: Kevin Moore <kevmoo@google.com> Reviewed-by: Kevin Moore <kevmoo@google.com>
…ackage_config, path, shelf, term_glyph, test_reflective_loader, webdev, webkit_inspection_protocol, yaml Revisions updated by `dart tools/rev_sdk_deps.dart`. cli_util (https://github.com/dart-lang/cli_util/compare/b0adbba..edcf1c3): edcf1c3 2022-11-15 Devon Carew blast_repo fixes (#71) csslib (https://github.com/dart-lang/csslib/compare/ba2eb2d..34203c0): 34203c0 2022-11-15 Kevin Moore blast_repo fixes (#154) dartdoc (https://github.com/dart-lang/dartdoc/compare/08e3098..dc502d0): dc502d08 2022-11-15 Sam Rawlins Move much PackageWarning logic _out_ of PackageGraph, into the enum. (#3251) ad651b15 2022-11-15 Sam Rawlins Move the e2e source-link test to a unit test (#3254) d14c680c 2022-11-11 Sam Rawlins Make many Strings in DocumentationComment non-nullable (#3243) 92afb9bb 2022-11-10 dependabot[bot] Bump github/codeql-action from 2.1.29 to 2.1.31 (#3246) http (https://github.com/dart-lang/http/compare/6339026..d56141d): d56141d 2022-11-11 Brian Quinlan Upgrade to ffigen ^7.2 and remove unnecessary casts (#820) d95a544 2022-11-10 Brian Quinlan Add a more complete implementation for `URLSessionTask`. (#818) intl (https://github.com/dart-lang/intl/compare/442193c..a127902): a127902 2022-11-16 Kevin Moore blast_repo fixes (#510) matcher (https://github.com/dart-lang/matcher/compare/6a9b83b..9051de0): 9051de0 2022-11-15 Kevin Moore blast_repo fixes (#197) mockito (https://github.com/dart-lang/mockito/compare/748e88e..347d3e4): 347d3e4 2022-11-14 Kevin Moore blast_repo fixes (#587) package_config (https://github.com/dart-lang/package_config/compare/cff98c9..abb4aec): abb4aec 2022-11-15 Kevin Moore blast_repo fixes (#127) path (https://github.com/dart-lang/path/compare/58ba22c..12ce876): 12ce876 2022-11-14 hellohuanlin Support more arguments in path.join API (#130) shelf (https://github.com/dart-lang/shelf/compare/5fd2593..1c21047): 1c21047 2022-11-11 Devon Carew update the no-response.yml configuration (#308) term_glyph (https://github.com/dart-lang/term_glyph/compare/ec7cf7b..822cd5b): 822cd5b 2022-11-15 Kevin Moore blast_repo fixes (#29) test_reflective_loader (https://github.com/dart-lang/test_reflective_loader/compare/ef934b7..52b6753): 52b6753 2022-11-15 Kevin Moore blast_repo fixes (#42) webdev (https://github.com/dart-lang/webdev/compare/22f6271..3ec168f): 3ec168f 2022-11-15 Anna Gringauze Add --enable-experience flag and pass it to the expression compiler service (#1794) 72272dd 2022-11-10 Elliott Brooks (she/her) Include a settings page for configuring the Dart Debug Extension (#1776) 73839e7 2022-11-10 Elliott Brooks (she/her) Log entire exception message instead of first line (#1782) webkit_inspection_protocol (https://github.com/google/webkit_inspection_protocol.dart/compare/b825c8f..ddb624c): ddb624c 2022-11-14 Kevin Moore blast_repo fixes (#95) yaml (https://github.com/dart-lang/yaml/compare/fda5b15..f699275): f699275 2022-11-15 Devon Carew Merge pull request #131 from dart-lang/blast_repo-2022_11_15T20_23_04 8f6a5f7 2022-11-15 Kevin Moore blast_repo fixes Change-Id: I5d55d733b7f9256edf4f44229cc810e827c23f7d Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/270240 Auto-Submit: Devon Carew <devoncarew@google.com> Commit-Queue: Kevin Moore <kevmoo@google.com> Reviewed-by: Kevin Moore <kevmoo@google.com>
Revisions updated by `dart tools/rev_sdk_deps.dart`. test (https://github.com/dart-lang/test/compare/92da93a..3ba78f1): 3ba78f15 2023-03-07 Bartek Pacia fix typo in architecture.md (#1966) tools (https://github.com/dart-lang/tools/compare/a1c3506..bed358e): bed358e 2023-03-07 Devon Carew rev to 0.1.0 (#29) webdev (https://github.com/dart-lang/webdev/compare/c007560..cfe9753): cfe9753 2023-03-07 Elliott Brooks (she/her) Update `dev` versions of DWDS and Webdev (#2022) c37d419 2023-03-07 Daniel Chevalier Fix for listening to custom streams in DWDS. (#2011) yaml (https://github.com/dart-lang/yaml/compare/a6d8781..1ad2f49): 0f80b12 revert updating the type for YamlScalar.value (#139) 1ad2f49 2023-03-01 Kevin Moore Require Dart 2.19, migrate to dart_flutter_team_lints, make associated fixes (#138) 4d369fd 2023-03-01 Kevin Moore benchmark: fix output.json (#137) yaml_edit (https://github.com/dart-lang/yaml_edit/compare/998eea2..6abc42a): 6abc42a 2023-03-08 Devon Carew updates for the next version of package:yaml (#45) 48e5868 2023-03-08 Kevin Moore blast_repo fixes (#46) aaa1d53 2023-03-02 Jonas Finnemann Jensen Add code coverage (#38) 0668eb5 2023-03-02 Jonas Finnemann Jensen Wrap recursively, prepare release (#28) a4ff857 2023-03-01 Mohamed Ishad Update CHANGELOG.md (#37) 2fdfbdb 2023-02-28 Mohamed Ishad Fix for issue #23 (#34) 494ad7c 2023-02-25 MikiPaul fixed typo (#36) Change-Id: I3aee0b2f84e97cf4f1131c002bb4e84ab8ffcc92 Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/287560 Commit-Queue: Devon Carew <devoncarew@google.com> Reviewed-by: Konstantin Shcheglov <scheglov@google.com>
Here's a minimal repro that this CL fixes: `ui.dart` ```dart library dart.ui; import 'dart:ffi'; part 'foo.dart'; ``` `foo.dart` ```dart part of dart.ui; @Native<Void Function()>(symbol: 'foo_func', isLeaf: true) external void foo_func(); ``` When compiling with `compile_platform.dart` with `--target=dart2wasm`, the following error appears: ``` Unhandled exception: Verification error: Target=wasm, VerificationStage.afterModularTransformations: Invalid location with target 'wasm' on FunctionNode() (FunctionNode): RangeError (offset): Invalid value: Not in inclusive range 0..56: 91 Context: 'foo_func_$import'. Node: 'FunctionNode()'. #0 VerificationErrorListener.reportError (package:kernel/verifier.dart:81:5) #1 VerifyingVisitor.problem (package:kernel/verifier.dart:222:14) #2 VerifyingVisitor._getLocation (package:kernel/verifier.dart:1361:7) #3 VerifyingVisitor._hasLocation (package:kernel/verifier.dart:1370:26) #4 VerifyingVisitor.getSameLibraryLastSeenTreeNode (package:kernel/verifier.dart:1342:28) #5 VerifyingVisitor.localContext (package:kernel/verifier.dart:1382:24) #6 VerifyingVisitor.defaultDartType (package:kernel/verifier.dart:1491:41) #7 Visitor.visitVoidType (package:kernel/visitor.dart:1309:37) #8 VoidType.accept (package:kernel/ast.dart:11190:42) #9 FunctionNode.visitChildren (package:kernel/ast.dart:3919:16) #10 VerifyingVisitor.visitChildren (package:kernel/verifier.dart:259:10) #11 VerifyingVisitor.visitWithLocalScope (package:kernel/verifier.dart:266:5) #12 VerifyingVisitor.visitFunctionNode (package:kernel/verifier.dart:721:5) #13 FunctionNode.accept (package:kernel/ast.dart:3908:38) #14 VerifyingVisitor.visitProcedure (package:kernel/verifier.dart:620:19) #15 Procedure.accept (package:kernel/ast.dart:3311:40) #16 visitList (package:kernel/ast.dart:14488:14) #17 Library.visitChildren (package:kernel/ast.dart:591:5) #18 VerifyingVisitor.visitChildren (package:kernel/verifier.dart:259:10) #19 VerifyingVisitor.defaultTreeNode (package:kernel/verifier.dart:196:5) #20 TreeVisitor.visitLibrary (package:kernel/visitor.dart:503:35) #21 VerifyingVisitor.visitLibrary (package:kernel/verifier.dart:367:11) #22 Library.accept (package:kernel/ast.dart:577:38) #23 visitList (package:kernel/ast.dart:14488:14) #24 Component.visitChildren (package:kernel/ast.dart:14320:5) #25 VerifyingVisitor.visitChildren (package:kernel/verifier.dart:259:10) #26 VerifyingVisitor.visitComponent (package:kernel/verifier.dart:342:7) #27 Component.accept (package:kernel/ast.dart:14313:38) #28 VerifyingVisitor.check (package:kernel/verifier.dart:171:15) #29 verifyComponent (package:kernel/verifier.dart:69:20) ... ``` The issue seems to be that after doing this native transformation, the node's `fileUri` references the enclosing library (`ui.dart` above), but the `node.location` references the actual source file (`foo.dart` above) indirectly through `node.fileOffset`. This ends up being an issue when compiling the platform dill in Google3, but I didn't look into why `flutter build web --wasm` isn't broken. Internal bug: b/292172146 Change-Id: I2b8d7d215b2c36354860257ce651d50168e9523d Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/315360 Reviewed-by: Ömer Ağacan <omersa@google.com> Commit-Queue: Jia Hao Goh <jiahaog@google.com>
This issue was originally filed by paulp...@gmail.com
Tailrec optimization is a well-known feature of functional languages.
I propose to add support for it in dart.
The text was updated successfully, but these errors were encountered: