Jump to content
  • Advertisement

MumbleFuzz

Member
  • Content Count

    120
  • Joined

  • Last visited

Community Reputation

188 Neutral

About MumbleFuzz

  • Rank
    Member
  1. MumbleFuzz

    Am I the only one?

    Quote:Original post by Sneftel If you add recursion (via a fixed-point operator), halting becomes undecidable. You can't have it both ways. Indeed, which is why I said it's not possible. I was just checking my earlier reasoning, which I thought Rebooted disagreed with. [Edited by - MumbleFuzz on November 28, 2007 7:17:37 AM]
  2. MumbleFuzz

    Am I the only one?

    Quote:Original post by Rebooted You can then look a program's type and see whether or not it uses general recursion, so you have a proof that a certain class of programs in the language terminate. Quote:Original post by Daerax Although I do think that turing completeness is overhyped, a language need not have this feature to be sufficient for nearly all computational needs. Like say the now defunct Charity. Interesting... I've never really studied the different classes of recursive functions, so I've always just taken Turing-completeness to be a benchmark for expressability. It's something I'll have to look into further [smile].
  3. MumbleFuzz

    Am I the only one?

    Quote:Original post by Rebooted That's true, STLC is not turing complete. It's the simplest type system that proves programs terminate, but there are others (it's not equivalent to solving the halting problem). I must admit I've never studied the formal properties of these languages in depth, but I was rather under the impression that recursion was the only feature missing from STLC which prevented it from being Turing-complete. Therefore, if one extended it with recursion, and then (hypothetically speaking) proved, for any program and input, whether or not a program terminates, would one not then have a solution to the halting problem? Perhaps I was a little vague, but this is what I had in mind.
  4. MumbleFuzz

    Am I the only one?

    Quote:Original post by Daerax Quote:Original post by MumbleFuzz Quote:Original post by Rebooted Can you show me a "dynamic" type system that can prove a program terminates (I think that might be difficult [smile]) I think that's a slightly unfair question, seeing as the simply-typed lambda calculus isn't Turing-complete... Where did you read this? I am certain that lambda -> is turing complete. perhaps you misattributed something on a constructive type theory sans recursion? For example a language which builds on a simply typed lambda calc is Haskell or Ocaml. The untyped lambda calculus is Turing-complete, but the simply typed lambda calculus by itself lacks recursion. This is because a fixed point combinator (which can be defined in terms of the untyped calculus) is impossible to type in this system. That's not to say you can't extend the calculus with new language features which are equivalent -- but at this point proof of termination is no longer possible (or else you would have solved the halting problem). Perhaps you already knew this and assumed "the simply typed lambda calculus" to refer to the language extended with, say, a fix operator. I don't believe that's standard in the literature, however, and it certainly isn't the language linked to by Rebooted. [Edited by - MumbleFuzz on November 27, 2007 4:14:10 AM]
  5. MumbleFuzz

    Am I the only one?

    Quote:Original post by Rebooted Can you show me a "dynamic" type system that can prove a program terminates (I think that might be difficult [smile]) I think that's a slightly unfair question, seeing as the simply-typed lambda calculus isn't Turing-complete... (Unless it turns out, for some curious reason, that most popular dynamically-typed languages aren't either. To be honest I really have no idea [smile].)
  6. MumbleFuzz

    Do you still make simple errors?

    As far as I know, today was the first time I've ever written this: if (foo = bar) { ... } Luckily it didn't take too long to spot the missing equality, 'cos it was the termination condition for a loop and resulted in a massive dialog appearing rapidly and repeatedly for no apparent reason. Generally, though, the only mistakes I make these days are design decisions. The syntax (of the languages I use regularly, anyway) is mostly second nature.
  7. MumbleFuzz

    [OOD] Patterns & Optimization

    Quote:Original post by Barius EDIT: I thought you could just apply a list of optimizers until "nothing changes anymore", but that might be too inefficient, since each optimizer will only work on a small part of the tree. Perhaps a more clever combination scheme for optimizers is necessary. I guess it depends on just "how optimal" the code should be. Scanning wikipedia, it sounds as though the requirements of whatever pattern you use will be determined a little by the kind of language you're implementing. How is memory modelled, for example? Will exploiting locality be a worthwhile task with your VM? Depending on what you want to do, the problem will very possibly be NP-complete. I guess heuristics are the way forward. Starting with your problem #2:Quote:These optimizations rely on properties of the manipulated objects (side-effects, inequality and equaliy relationships, etc) that are not part of the user-side interface of my objects (they don't need it), but I need a way to transmit these properties simply from object to object, and also to add them when I start needing them.I do wonder whether a fancy new design pattern is really needed here. For one thing, some optimization techniques will require relatively global information (where references are allocated, how they're used, what happens to values later on in the code, and so on). It may be easier, rather than trying to pass this information around from one Optimizer class to another, simply to annotate the syntax tree in one or more passes with the information needed, and then to optimize that. (EDIT: Although you say you don't want to add this information until it's needed, as far as I can see you probably wouldn't need to include more than information about the location of each term in the tree (i.e. the scope at which it exists, and the scope at which it is used), and perhaps how it's allocated. Each Optimizer can then deduce further information from the syntactical structure of the surrounding code if needed. If you find you need to add optimization-specific information to the tree, then see my edit below.) This makes #1 easier:Quote:I have a large number of optimization opportunities, both present and future, and I need to be able to add them in an elegant and efficient way when the time comes—I don't want to add them from the start just in case they aren't necessary.Jut use a standard visitor/possibly policy/pattern matching approach and traverse the tree. But #3 is still interesting:Quote:# These optimizations should naturally cascade: in the above example, the loop could be collapsed to { x = max; }. Then, if x is not used anywhere outside the loop, there's no need for that, so the statement is collapsed to {}. But then, if max was a variable set as the sole side-effect of a loop right before that, then the entire loop loses its side-effect and becomes { x = max; } as well, and so on.There are a few subtleties here. One is that the order in which you apply optimizations may be important (though presumably this will depend on what optimizations you can apply to your language; you may have to prove certain properties about each). This would be where the heuristics come in. The algorithm is then a case of asking each optimization in the list to compute just how significant its affect may be, applying the most useful optimization, and then repeating (also recursively) until no more can be applied. Don't forget to reannotate the affected parts of the tree; you can get each optimizer to do this as it applies itself. Also make sure that each optimizer checks that any semantic affects resulting from changes made to the subtree it's given will be local to that subtree (e.g. don't make variables more local if they're used in an enclosing scope). Please bear in mind, though, that I don't know anything about optimization and I just made this up in a few minutes. There are probably a whole host of flaws and gaps in the idea. Finally, I would personally not want to implement this in an imperative language: it's just crying out for pattern matching of some kind. Are you sure you can't use ocaml? ;-) (EDIT 2: In case you need to add information to the annotated nodes which is specific to each Optimizer... 1. Have each annotated node include a map from Optimizers to a new kind of tag information class. Derive subclasses of this tag information class for each type of Optimzer. (The information can be safely retrieved using double dispatch or pattern matching.) 2. When each Optimizer is asked to examine a term (or subterm) in the tree, have it add the information, in the form of the appropriate tag information class, to the annotated term's map using the Optimizer as the key. 3. When applied to a subterm, the Optimizer can then lookup the node in the tree at which this information would be stored by referring to the location information in the subterm's tag. 4. The information can then be retrieved safely from the map.) [Edited by - MumbleFuzz on August 10, 2007 5:11:18 AM]
  8. Quote:Original post by Nathan Baum That doesn't make sense. It's true that a multiple assignment isn't a tuple, but that's because "multiple assignment" and "tuple" describe entirely different things. You may as well complain that a function call isn't a string. That was precisely my point. EDIT: But you're right to include your alternative #3. I was so confused by the boxing construct at first that I forgot what the original tuple assignment was for. [Edited by - MumbleFuzz on July 27, 2007 9:48:01 AM]
  9. Quote:I added this operator to make it so that I can easily make templated containers. For example the list template takes a type as a template parameter for its element type. Using the boxing operator allows you to store boxed tuples in a list.Ah. Do I take it you don't have typing rules for tuples? Is there any particular reason for this? EDIT: Oh. I see what you've done. In your example, you seem to be taking (x,y) = (5,6) to be a shorthand for x = 5; y = 6;. Which is neat: multiple assignments are groovy. What they are not, however, is tuples. I believe you are mixing the two. Your problem would therefore be best solved in one of two ways: 1. Keep tuples and find a new syntax for multiple assignments. 2. Keep your current syntax for multiple assignments and discard tuples. Once you've got records, you've effectively got tuples anyway. As a final note, I think you would have noticed this for yourself had you given tuples a typing rule. And in any case, a language without typing rules for even a single term cannot be type safe, so unless you have typing rules for every construct, you may as well remove the type system altogether. [Edited by - MumbleFuzz on July 26, 2007 3:48:54 PM]
  10. I'm not sure I entirely follow. What is the purpose of the boxing construct when you already have tuples? In your example...int x, int y; (x,y)=(5,6)...presumably the type of (x,y) is something like (int, int) or int * int? If that is the case, then surely [int, int]m and (int, int)m would declare variables that behave in the same way (modulo the type)? So then why not keep the boxing notation solely for records (which effectively generalize tuples by naming the fields)? Finally, I believe that [int x, int y] && [int y, int z] should not be a well typed term. You should require that the sets of names of fields in two record types be disjoint when the records are combined in this manner.
  11. Quote:Original post by Rebooted This should work: eval :: Term -> Term eval (App (Abs t12), v2) | isval v2 = subst 0 v2 t12 eval (App (v1, t2) | isval v1 = App (v1, eval t2) eval (App (t1, t2)) = App(eval t1, t2) Yup. Fantastic! Many thanks, Rebooted.
  12. I'm trying to throw together a small language (currently just the untyped lambda calculus) interpreter. Eventually I'll have to write it in OCaml, but for the time being I thought I'd try Haskell. It's been a while since I used the language, though, and I'm trying to remember if there's a way to write the following function: eval :: Term -> Term eval (App (Abs t12), v2) when isval v2 = subst 0 v2 t12 eval (App (v1, t2) when isval v1 = App (v1, eval t2) eval (App (t1, t2)) = App(eval t1, t2) (The type Term is given by: data Term = Var Int | Abs Term | App (Term, Term).) The equivalent function in OCaml would match the first line of the definition only when the predicate isval v2 is true. Is there a similar clause in Haskell, or an otherwise neat way to write the function? Currently the best I can come up with is: eval :: Term -> Term eval (App(t1,t2)) | isval t1 && isval t2 = subst 9 t2 t12 | isval t1 = App(t1, eval t2) | otherwise = App(eval t1, t2) where t12 = get_abs_term t1 get_abs_term (Abs t12) = t12 which I suppose is ok; but as the eval function becomes more complex (which it will do), I suspect that more and more definitions will have to be given in the where clause, and I think readability will suffer. Any suggestions on how I might write it? Like I say, I'm not too familiar with Haskell, so I'm probably missing something simple.
  13. MumbleFuzz

    Dynamic 3D Arrays

    Quote:Original post by AltecZZ I get this error on the first line: unsigned int *** imageData = unsigned int ** [IMAGE_SIZE]; VS2005 complains about type 'unsigned int' unexpected Try: unsigned int *** imageData = new unsigned int ** [IMAGE_SIZE];
  14. MumbleFuzz

    Good haskell books

    Quote:Original post by chollida1 Quote:Original post by MumbleFuzz I'm quite a fan of Introduction To Functional Programming by Richard Bird. Despite what the reviews say (they claim it's not a book for beginners), I found it to be a good introduction to a language I'd never used before. I found that "Introduction to Functional programming" Did give a decent background to functional programming but it read too much like a university text for my liking and its more expensive:) IMHO If you want to learn Haskell that's not the book for you as Haskell is just the vehicle he uses to get the theorey across. Having said that, if your goal is to learn the theory of functional programming rather than Haskell itself then perhaps that book could be a winner? I guess that's probably true -- I was more interested in the theory of functional programming as a paradigm at the time (in fact, I was taking Bird's course). Since I tend to program in imperative languages, it was a refreshing change, and extremely insightful.
  15. MumbleFuzz

    Good haskell books

    I'm quite a fan of Introduction To Functional Programming by Richard Bird. Despite what the reviews say (they claim it's not a book for beginners), I found it to be a good introduction to a language I'd never used before.
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!