5 ms·

I created a non-Turing complete programming language for editing animations, implemented as a GIMP Script-Fu script (Scheme, basically). Here's the documentatio

by Grue3 10y ago

I created a non-Turing complete programming language for editing animations, implemented as a GIMP Script-Fu script (Scheme, basically). Here's the documentation: http://tshatrov.github.io/animstack http://tshatrov.github.io/animstack Why? Because in GIMP it's annoying to edit animations with many layers, so I wanted to write a script that would do what I want. But rather than hardcoding a specific action, I wrote it in an extensible way, and the rest is history. In general, I think non-Turing complete (always terminating) languages are super useful and should be used more often.

yjftsjthsd-h 10y ago
Non-Turing complete languages are useful, but it has been my impression that it is difficult to be powerful enough to be useful without being (accidentally!) Turing complete.
- sova 10y ago
  As a Computer Scientist, I actually find the distinction Turing and non-Turing to be rather obscure. Perhaps I am in the ignorant minority on this.
  - sgt101 10y ago
    Isn't it just possessing both conditionals and loops?
    - omegaham 10y ago
      One more thing - memory. A Turing Machine is literally just a tape, a movable reader/writer, and a bunch of states that dictate what the reader/writer does. As long as you have memory, the ability to write to memory, conditionals, and some form of looping, whether it's a `while` loop, a `for` loop, or a `jmp` or `GOTO` instruction, it's Turing complete. Note that a conditional jump (`jne`, for example) satisfies both of the latter.
      - sgt101 10y ago
        yup memory. yup. I forgot...
        sova 10y ago
        "Conditionals, loops, and memory" is an interesting list of requirements, because "memory" can be abstracted into anything. Functional Languages rely on the fact that the same code shall always produce the same outcome, and thus the "tape" has been changed into a series of concrete blocks. That said, I don't think anyone would argue that functional languages are not TC, but it is interesting to consider that the Tape becomes code in Lisp...
      - kazinator 10y ago
        "Turing Complete" refers to a system which can be configured to be come any Turing Machine. When we write a particular program in some language and run it on some input, we have a Turing Machine. If the language lets us create any Turing Machine (i.e. do any Turing computation), then it is a Universal Turing Machine, and Turing Complete. Turing's Tape Machine is a UTM because the tape can be initialized with contents to turn it into any TM. Any calculation for which there is a TM can be done by the UTM (if someone can figure out what to put on the tape).
    - jcoffland 10y ago
      Not necessarily. Purely functional languages, like Lisp, do not have loops. Instead they have recursion. Any iterative algorithm (I.e. one with loops) can provably be converted to a recursive algorithm with out iteration.
      - kazinator 10y ago
        Lisp has loops: For instance, the do operator: (do ((i 0 (+ i 1))) ((> i 10)) (print i)) Or the loop macro: (loop for x below 5 and y in '(a b c d e) collecting (list x y)) The 1965 manual for Lisp 1.5 describes the prog construct, which persists into ANSI CL. Inside prog we can have labeled statements to which we can branch unconditionally with go in any direction. Lisp also has mutable variables. The following example from the Lisp 1.5 Programmer's Manual is still valid code today: (LAMBDA (A) (PROG (B) S (SETQ B A) (COND ((NULL B) (RETURN C))) (SETQ C (CONS (CAR A) C)) (GO S)))
      - smrq 10y ago
        While another commenter has mentioned that this is technically not correct with Lisp, it holds for the lambda calculus. You don't need loops to be TC if you have recursion. And for that you don't even need named functions-- note the URL of this site!
        kazinator 10y ago
        However, lambda calculus doesn't have code made of data, QUOTE or any of that. Lambda calculus isn't Lisp; it captures the gist of some of the evaluation semantics of Lisp only.
      - Shorel 10y ago
        Lisp is more multi-paradigm than pure functional. And we like it that way. It can be functional, object oriented, aspect oriented, etc.
  - deleted 10y ago
    [deleted]
  - scott_s 10y ago
    A Turing-complete programming language just means that you can compute anything that can be computed using that language. In other words, it can be used to write arbitrary computations. You don't need much to achieve this; off the top of my head, I think that being able to read and write to storage, basic addition, conditionals and loops are enough. (Formally, it means that your language can be used to simulate a single-taped Turing machine.) A non-Turing-complete language is any language which does not have one of those capabilities. Because the bar is so low, most languages you have used in your life are Turing-complete. For example, you can imagine a simple calculator-like language for just writing mathematical expressions. It can do all basic math operations, has conditions, but no ability to repeat things (no loops or recursion). That language is not Turing-complete. You can trivially prove that programs from such a language will finish - they can't not! there's no ability to impede progress.
    - blackkitty 10y ago
      You can actually have a turing complete instruction set with only one instruction. I am not sure as to the practicality but here is a wikipedia link to read. https://en.wikipedia.org/wiki/One_instruction_set_computer https://en.wikipedia.org/wiki/One_instruction_set_computer
- ASipos 10y ago
  Well, always-terminating implies non-Turing-complete, so that's a way to guarantee it. The proof is easy: just set for all n, f(n) to be the nth program in your toy language in lexicographical order and then set for all n, g(n):=f(n)(n) + 1. This g is clearly Turing-computable (you can modify an interpreter to compute it) and not in your language (a la Cantor).
- chewxy 10y ago
  Actually non-Turing languages are very useful and can be quite powerful. Consider for example TensorFlow and/or Theano. Before they added the loop and conditional Ops, they were non-Turing Complete. And you could do amazing things with it as it were. In fact, I took a lesson from that when working on Gorgonia (https://github.com/chewxy/gorgonia https://github.com/chewxy/gorgonia) - I don't ever want it to be a Turing Complete language.
berdario 10y ago
> In general, I think non-Turing complete (always terminating) languages are super useful and should be used more often. yup, always-terminating functions are also called total functions (if they're defined for every input). Which is a related concept to Total functional programming http://docs.idris-lang.org/en/latest/tutorial/theorems.html#totality-checking http://docs.idris-lang.org/en/latest/tutorial/theorems.html#... While Idris is turing complete for example, it's possible to mark functions and whole modules as total, and let the compiler prove it for you. Wish that more people knew that we have such tools available nowadays
- dualogy 10y ago
  Nice one, I wish there was a Haskell extension for that! (Can't risk switching existing/pending code-bases over to Idris just for that feature though)
  - a-saleh 10y ago
    I remember reading about two projects og Gabriel Gonzales that might be interesting in this regard. Dhall, a total configuration language. https://github.com/Gabriel439/Haskell-Dhall-Library https://github.com/Gabriel439/Haskell-Dhall-Library There is Morte and Anna as well, that look like the previous experiments in total languages in haskell. https://github.com/Gabriel439/Haskell-Annah-Library https://github.com/Gabriel439/Haskell-Annah-Library
agumonkey 10y ago
Deep down I believe GIMP's ergonomy is a plot to push people to write Scheme DSLs.
Peaker 10y ago
That they are always terminating is very useful for programs that generate proofs, or otherwise don't have to be evaluated. But if you can encode the Ackermann function, proof of termination is not very useful in practice - as it may consume arbitrarily large amounts of space and time to evaluate (easily more than the age/size of the universe).

by Grue3 10y ago

yjftsjthsd-h 10y ago

Non-Turing complete languages are useful, but it has been my impression that it is difficult to be powerful enough to be useful without being (accidentally!) Turing complete.

sova 10y ago
As a Computer Scientist, I actually find the distinction Turing and non-Turing to be rather obscure. Perhaps I am in the ignorant minority on this.
- sgt101 10y ago
  Isn't it just possessing both conditionals and loops?
  - omegaham 10y ago
    One more thing - memory. A Turing Machine is literally just a tape, a movable reader/writer, and a bunch of states that dictate what the reader/writer does. As long as you have memory, the ability to write to memory, conditionals, and some form of looping, whether it's a `while` loop, a `for` loop, or a `jmp` or `GOTO` instruction, it's Turing complete. Note that a conditional jump (`jne`, for example) satisfies both of the latter.
    - sgt101 10y ago
      yup memory. yup. I forgot...
      - sova 10y ago
        "Conditionals, loops, and memory" is an interesting list of requirements, because "memory" can be abstracted into anything. Functional Languages rely on the fact that the same code shall always produce the same outcome, and thus the "tape" has been changed into a series of concrete blocks. That said, I don't think anyone would argue that functional languages are not TC, but it is interesting to consider that the Tape becomes code in Lisp...
    - kazinator 10y ago
      "Turing Complete" refers to a system which can be configured to be come any Turing Machine. When we write a particular program in some language and run it on some input, we have a Turing Machine. If the language lets us create any Turing Machine (i.e. do any Turing computation), then it is a Universal Turing Machine, and Turing Complete. Turing's Tape Machine is a UTM because the tape can be initialized with contents to turn it into any TM. Any calculation for which there is a TM can be done by the UTM (if someone can figure out what to put on the tape).
  - jcoffland 10y ago
    Not necessarily. Purely functional languages, like Lisp, do not have loops. Instead they have recursion. Any iterative algorithm (I.e. one with loops) can provably be converted to a recursive algorithm with out iteration.
    - kazinator 10y ago
      Lisp has loops: For instance, the do operator: (do ((i 0 (+ i 1))) ((> i 10)) (print i)) Or the loop macro: (loop for x below 5 and y in '(a b c d e) collecting (list x y)) The 1965 manual for Lisp 1.5 describes the prog construct, which persists into ANSI CL. Inside prog we can have labeled statements to which we can branch unconditionally with go in any direction. Lisp also has mutable variables. The following example from the Lisp 1.5 Programmer's Manual is still valid code today: (LAMBDA (A) (PROG (B) S (SETQ B A) (COND ((NULL B) (RETURN C))) (SETQ C (CONS (CAR A) C)) (GO S)))
    - smrq 10y ago
      While another commenter has mentioned that this is technically not correct with Lisp, it holds for the lambda calculus. You don't need loops to be TC if you have recursion. And for that you don't even need named functions-- note the URL of this site!
      - kazinator 10y ago
        However, lambda calculus doesn't have code made of data, QUOTE or any of that. Lambda calculus isn't Lisp; it captures the gist of some of the evaluation semantics of Lisp only.
    - Shorel 10y ago
      Lisp is more multi-paradigm than pure functional. And we like it that way. It can be functional, object oriented, aspect oriented, etc.
- deleted 10y ago
  [deleted]
- scott_s 10y ago
  A Turing-complete programming language just means that you can compute anything that can be computed using that language. In other words, it can be used to write arbitrary computations. You don't need much to achieve this; off the top of my head, I think that being able to read and write to storage, basic addition, conditionals and loops are enough. (Formally, it means that your language can be used to simulate a single-taped Turing machine.) A non-Turing-complete language is any language which does not have one of those capabilities. Because the bar is so low, most languages you have used in your life are Turing-complete. For example, you can imagine a simple calculator-like language for just writing mathematical expressions. It can do all basic math operations, has conditions, but no ability to repeat things (no loops or recursion). That language is not Turing-complete. You can trivially prove that programs from such a language will finish - they can't not! there's no ability to impede progress.
  - blackkitty 10y ago
    You can actually have a turing complete instruction set with only one instruction. I am not sure as to the practicality but here is a wikipedia link to read. https://en.wikipedia.org/wiki/One_instruction_set_computer https://en.wikipedia.org/wiki/One_instruction_set_computer
ASipos 10y ago
Well, always-terminating implies non-Turing-complete, so that's a way to guarantee it. The proof is easy: just set for all n, f(n) to be the nth program in your toy language in lexicographical order and then set for all n, g(n):=f(n)(n) + 1. This g is clearly Turing-computable (you can modify an interpreter to compute it) and not in your language (a la Cantor).
chewxy 10y ago
Actually non-Turing languages are very useful and can be quite powerful. Consider for example TensorFlow and/or Theano. Before they added the loop and conditional Ops, they were non-Turing Complete. And you could do amazing things with it as it were. In fact, I took a lesson from that when working on Gorgonia (https://github.com/chewxy/gorgonia https://github.com/chewxy/gorgonia) - I don't ever want it to be a Turing Complete language.

berdario 10y ago

> In general, I think non-Turing complete (always terminating) languages are super useful and should be used more often. yup, always-terminating functions are also called total functions (if they're defined for every input). Which is a related concept to Total functional programming http://docs.idris-lang.org/en/latest/tutorial/theorems.html#totality-checking http://docs.idris-lang.org/en/latest/tutorial/theorems.html#... While Idris is turing complete for example, it's possible to mark functions and whole modules as total, and let the compiler prove it for you. Wish that more people knew that we have such tools available nowadays

dualogy 10y ago
Nice one, I wish there was a Haskell extension for that! (Can't risk switching existing/pending code-bases over to Idris just for that feature though)
- a-saleh 10y ago
  I remember reading about two projects og Gabriel Gonzales that might be interesting in this regard. Dhall, a total configuration language. https://github.com/Gabriel439/Haskell-Dhall-Library https://github.com/Gabriel439/Haskell-Dhall-Library There is Morte and Anna as well, that look like the previous experiments in total languages in haskell. https://github.com/Gabriel439/Haskell-Annah-Library https://github.com/Gabriel439/Haskell-Annah-Library

agumonkey 10y ago

Deep down I believe GIMP's ergonomy is a plot to push people to write Scheme DSLs.

Peaker 10y ago

That they are always terminating is very useful for programs that generate proofs, or otherwise don't have to be evaluated. But if you can encode the Ackermann function, proof of termination is not very useful in practice - as it may consume arbitrarily large amounts of space and time to evaluate (easily more than the age/size of the universe).