## User login## Navigation |
## LtU Forum## Inference of Polymorphic RecursionIn the following (Haskell) example, the type annotation on f :: a -> (Int, a) f x = (g True, x) g True = 0 g False = fst (f 'a') + fst (f 0) main = do print (fst (f True))
I can understand why in general, but I wonder if we could just decide to generalize arbitrarily in the order that declarations appear so that in this case the type of Thanks ## Generic overload resolutionKitten has ad-hoc static polymorphism in the form of
This is checked with the standard “generic instance” subtyping relation, in which
But this raises a problem: I want to select the That is, for ## UnsoundnessHi, I wonder if someone can help resolve the conflict described below. My system is an Algol like language which supports both functional and procedural code. (x=1,y=42.1) which has type (x:int, y:double) then this is a first class value, and the field names are projections: x (x=1,y=42.1) Since I have overloading there's no conflict with the same field name in some other record, (x=1,y=42.1) . x Now, to get rid of lvalues we introduce pointer types and variables so that in var xy = (x=1,y=42.1); &xy <- (x=2,y=43.1); This is really cool because To assign to a component, we introduce a second overload for each projection that takes a pointer argument and returns a pointer: &xy . x <- 3;
This works for other products as well (tuples, arrays and structs). So far so good, but now I have another feature called "compact linear types" The problem is .. compact linear type components are not addressable. And so the conflict: polymorphic pointer projections are unsound: proc f[T,U] (r: &(T,U)) (v:T)) { r.0 <-v; } will not work if r is a pointer to a compact linear object. I can think of three solutions: (1) invent a new pointer type (destroys uniform pointer representation property) ## Domain specific language for playing gamesWriting computer games for people to play, even quite simple ones, is a surprisingly challenging task. Here I'm thinking of turn-based games like card and board games, puzzles, block-pushing and perhaps simple arcade games like Space Invaders. It would seem fairly obvious that large parts of the heavy lifting will be common from one to another and that differences in game play might well be encapsulated in a DSL. Others have had the same thought. Here are links to some good reviews: https://chessprogramming.wikispaces.com/General+Game+Playing, https://en.wikipedia.org/wiki/Domain-specific_entertainment_language, https://en.wikipedia.org/wiki/General_game_playing. The GGP language GDL is a Datalog derivative, Zillions uses a Lisp dialect and Axiom is a kind of Forth. There are several others, including PuzzleScript, CGL and VGDL. GGP in particular is the focus of a lot of AI work, not so much the UI. Several of these projects appear dormant. Considering the prevalence of games in the community and the number of people involved in writing them, this looks like surprisingly little effort in this direction. I was wondering if anyone is aware of or involved in any active work in this area, particularly on the language side, before I go and invent my own. ## Process Network for Effects, Monad AlternativeMonads are an awkward effects model in context of concurrency. We get incidental complexity in the form of futures or forking threads with shared memory. The running program becomes entangled with the environment, which hinders persistence and mobility and debugging. So I sought alternatives in literature. Kahn Process Networks (KPNs) seem like a very good alternative. From an external perspective, they share a lot of similarities to monads, except we get more than one input (continuation) and output (effect) port and thus can model concurrent operations without relying on effects or environment support. Internally, KPNs have a lot of similarities to free monads: we can compose KPNs to handle effects internally, translate them, etc.. Use of KPNs as first class values allows for dynamic structure and mobile processes. The main feature missing from KPNs is the ability to work with asynchronous inputs. But it is not difficult to add time to the model, and thus support asynchronous messaging and merges in a style similar to functional-reactive or flow-based programming (and somewhere between the two in terms of expressiveness). I doubt this is a new idea. I've written about these ideas in more detail on my blog: - KPNs as an Effects Model - a pure alternative to monads.
- Reactive Process Networks - add a simple time model to KPNs.
Reactive KPNs with open ports or channels also make a better FRP than most, having a far more direct API for pushing inputs and pulling outputs deep within a network. ## Defining recursive function as a monad (or other solutions)Is it possible to create recursive function using monads in a functional language? definition of monad in a functional language should look like: " The reason I'm asking is that I'm defining a language where functions are passed around together with applied parameters. If I repeatedly call a function by a recursion, new data sums with previous data that was there before the recusion was applied. So finally I'd get a set of all intermediate results, while I'm interested only in the final result. I'm not even sure if monads would work in this environment with data stitched to function calls. Actually, a solution I can use is first to create a set of parameters of each recursion step, and then to call some kind of fold function over the set that produces a single result. But I want to explore other possibilities, so I'm interested in monadic or other solutions. Thank you for your time. ## Eliminating left recursionDoes anyone have a reference to a correct algorithm which eliminates left recursion from a grammar? The one in Wikipedia is incorrect. Lots of youtube videos and lecture notes Google finds are also incorrect. All make the same mistake, they forget that a production A = N A X is left recursive if N is nullable. Requiring the grammar to be null free would be absurd since the algorithm itself inserts epsilon productions. I also wish to extend the requirement to an attribute grammar of the form usually used in practice, with an extra symbol kind for AST construction, etc, which cannot be eliminated and yet recognises the empty string. BTW: I'm looking for the basic algorithm. Lost my copy of the Dragon Book ;( ## Splitting witnesses upHi, I have an idea for an academic paper, and am seeking help for prior art and research. My idea is about proof witnesses, and what to do when a group of witnesses contradict each other (software bug/logical inconsistency), and repairing the proof. Without going into details on the algorithm, the metaphor is simply to split witnesses up, using a mathematical plane to draw a group of witnesses into two groups: definitely lying (the witness whose account is proven contradictory/false), and somewhat certain (witnesses with similar testimonies who have not yet been proven contradictory/false, but might once asked further questions or may be proven "good enough" given the new questions/evidence we've asked the witness about). My idea comes from witness interrogation techniques in the real world. Since I haven't been active in PLT for several years, my knowledge of what to search for and keywords to use on ACM and IEEE search engines is pretty weak, and I could use some tips. Thank you very much! ## Any recent developments on "active libraries" that I'm missing?I'm interested in libraries that guide compilers for optimizations, but it - Papers like "Generative Programming and Active Libraries" which usually just - There's a thesis, "Active Libraries and Universal Languages", which as far as Two implementations that work well: - I think Haskell libraries that use GHC's rewrite rules are "active libraries" - The stream fusion library described in POPL'17 paper "Stream Fusion, to These are pretty much all I can think of as examples. I'm looking for recent ## Resources for implementing higher-kinded types?I’m working on a language and I would like to implement polymorphism over type constructors (for functor, applicative, monad, etc.) but I’m uncertain how to proceed. Can anyone recommend tutorial-style resources or sample implementations of this? I’ve read that higher-order unification is involved, and that inference is undecidable without certain restrictions. Is that accurate? Would it be difficult to retrofit a (more or less) standard implementation of Hindley–Milner? |
## Browse archives## Active forum topics |

## Recent comments

1 day 11 hours ago

1 day 11 hours ago

1 day 13 hours ago

1 day 14 hours ago

1 day 22 hours ago

2 days 5 hours ago

2 days 6 hours ago

3 days 7 hours ago

3 days 14 hours ago

3 days 17 hours ago