3 ms·

Also, the definition of an infinite list of ones ones = 1 : ones is a non-function value, but is recursively applied to itself. Might help illustrate why

by alipang 15y ago

Also, the definition of an infinite list of ones ones = 1 : ones is a non-function value, but is recursively applied to itself. Might help illustrate why this is a useful notion in Haskell.

lurker14 15y ago
To be precise. "ones" is not "recursively applied to itself". "ones" is not a function. "(:)" is a function. In actuality, "ones" is both an argument and a result of the (:) function (aka "cons"). This works in Haskell because "ones" is not an atomic value or function; "ones" is a "lazy" structure, where some of the elements's values depend on other element's values, and Haskell uses a "call-by-need" graph reduction algorithm to evaluate arbitrarily complex* computations down to values, not in any sort of sraihtforward order suggested by "argument -> function -> result -> lvalue" in an imperative or strict language. Laziness is at the core of the runtime system's model for computing a result from a program, and it's not something you can translate line-by-line from a non-lazy program, even a functional language program. I'm not just being pedantic. Haskell (with a runtime like GHC, required for this conversation to really make sense) really is different from other programming systems. ("Programming system"! Not just "language"!). The runtime system ("RTS") is not just a C runtime that provides a statement language and shim over OS system calls. The RTS is not "just" a VM like Java VM. The RTS is (metaphorically) like perl's "perl -nple" or a SQL RDBMS query planner, where the runtime is itself a program that takes your code as input and does its own extremely sophisticated computation that is not at all visible in your program's code. [] Arbitrarily* complex, but still "causal" structures that admit at least one valid order of evaluation. Trying to define "ones = ones" or other non-disentanglable cyclic dependencies leads to a runtime failure ("<loop>" exception). [] In some cases, the graph solver might practically fail to solve a graph that is theoretically solvable. Let's ignore that.
- gtani 15y ago
  That's good info, GHC is an pretty amazing feat of engineering, there are some good summaries of STG, C--, etc for further reading: http://darcs.haskell.org/ghc/docs/comm/the-beast/stg.html http://darcs.haskell.org/ghc/docs/comm/the-beast/stg.html http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/StgSynType http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler... http://www.reddit.com/r/programming/comments/i4jb1/haskells_evaluation_isnt_magic/c21369j http://www.reddit.com/r/programming/comments/i4jb1/haskells_... ------------- Also, Simon M started Google +ing about what he's up to https://plus.google.com/u/0/107890464054636586545/posts https://plus.google.com/u/0/107890464054636586545/posts

by alipang 15y ago

Also, the definition of an infinite list of ones ones = 1 : ones is a non-function value, but is recursively applied to itself. Might help illustrate why this is a useful notion in Haskell.

lurker14 15y ago

To be precise. "ones" is not "recursively applied to itself". "ones" is not a function. "(:)" is a function. In actuality, "ones" is both an argument and a result of the (:) function (aka "cons"). This works in Haskell because "ones" is not an atomic value or function; "ones" is a "lazy" structure, where some of the elements's values depend on other element's values, and Haskell uses a "call-by-need" graph reduction algorithm to evaluate arbitrarily complex* computations down to values, not in any sort of sraihtforward order suggested by "argument -> function -> result -> lvalue" in an imperative or strict language. Laziness is at the core of the runtime system's model for computing a result from a program, and it's not something you can translate line-by-line from a non-lazy program, even a functional language program. I'm not just being pedantic. Haskell (with a runtime like GHC, required for this conversation to really make sense) really is different from other programming systems. ("Programming system"! Not just "language"!). The runtime system ("RTS") is not just a C runtime that provides a statement language and shim over OS system calls. The RTS is not "just" a VM like Java VM. The RTS is (metaphorically) like perl's "perl -nple" or a SQL RDBMS query planner, where the runtime is itself a program that takes your code as input and does its own extremely sophisticated computation that is not at all visible in your program's code. [] Arbitrarily* complex, but still "causal" structures that admit at least one valid order of evaluation. Trying to define "ones = ones" or other non-disentanglable cyclic dependencies leads to a runtime failure ("<loop>" exception). [] In some cases, the graph solver might practically fail to solve a graph that is theoretically solvable. Let's ignore that.

gtani 15y ago
That's good info, GHC is an pretty amazing feat of engineering, there are some good summaries of STG, C--, etc for further reading: http://darcs.haskell.org/ghc/docs/comm/the-beast/stg.html http://darcs.haskell.org/ghc/docs/comm/the-beast/stg.html http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/StgSynType http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler... http://www.reddit.com/r/programming/comments/i4jb1/haskells_evaluation_isnt_magic/c21369j http://www.reddit.com/r/programming/comments/i4jb1/haskells_... ------------- Also, Simon M started Google +ing about what he's up to https://plus.google.com/u/0/107890464054636586545/posts https://plus.google.com/u/0/107890464054636586545/posts