Representing a Transducer Systems in sml

Question

I need help writing code such that:

Given two functions, say f1 and f2 and an initial input i1 for f1, I will feed i1 to f1 and whatever ouptput it returns, I will feed to f2 and whatever f2 returns I will feed to f1 and so on...

Thus it will look like this: fun pair(m1, m2, i1) = ...

m1 and m2 here actually represent Finite State Transducers such that m1 = (state, f1). the state here is the inital state we have i1. f1 takes in (state, input) and returns an output (next state, oput) the oput is then feeded to m1 and so on..

For clarification, this represents a Transducer Systems. This means that Two FSTs with complementary inputs and outputs can be run in parallel, with the output of each serving as the input for the other.

This is supposed to return say a the list of outputs generated.

To help I have already wrote a function run that takes in a fst m and a list of inputs, gives out the list of outputs obtained by running m on the inputs.

However my head flipped when trying to write this function cause I kinda entered an infinite loop, also my code was unbelievably long while this can be done easily using my helper function run.

Any ideas?

Answer 1

Thank you for the push spela! Your ideas are in the right track.

So typically here is how it goes: You do in fact use lazy evaluation. Here we work with our own lazy structure anyhow(you can create your own structures in ml).

Using the function run i mentioned earlier, I can make a function that runs m1 on i1 and then call it in an mutually recursive function jest beneth it. Finally I will call the function all together! Here is how it wil look like:

  fun pair(m1, m2, i1)=
    let
      fun p1 () = run (m1) (delay(fn() => Gen(i1,p2())))
      and p2 () = run (m2) (p1())
    in
      p1()
    end

Here delay and Gen are part of my structure. Gen represents a stream with i1 as the first element and p2() as the rest. delay takes in a function and typically represents the laziness part in this implementation. Using mutually recursive functions (functions that call each other, enabled by typing "and" instead of "fun" like above) I could go back and forth and so on.

There is another simpler method to implement this believe it or not, but this is for starters. If you can any way to improve this answer(or another solution) you are welcome to share! Thank you

Answer 2

Interesting question. I think you should somehow use a lazy evaluation. I'm not sure how to use it since I never did that and I have to admit I didn't really dig into it, but after short "googleing" I think I can provide a few useful links.

So, my first guess was:

fun pairFirst f1 f2 i1 =
    fn () => pairFirst f2 f1 (f1 i1)

as you would do it in LISP, but it obviously doesn't work in SML. So I googled it.

First, I found out that SML actually does support lazy evaluation: http://www.cs.cmu.edu/~rwh/introsml/core/lazydata.htm

Quote: "First off, the lazy evaluation mechanisms of SML/NJ must be enabled by evaluating the following declarations:

Compiler.Control.Lazy.enabled := true; open Lazy;"

I tried it, but it also didn't work, so I googled some more: https://github.com/trptcolin/euler-sml/blob/master/lazy_utils.sml

Quote: " (* most lazy details are from Programming in Standard ML, Robert Harper * notable exception: Compiler.Control.Lazy.enabled has moved to Control.lazysml *)

Control.lazysml := true; open Lazy;"

From the content of these two links, I constructed my second guess:

Control.lazysml := true;
open Lazy;

fun lazy pair (f1: 'a -> 'a, f2: 'a -> 'a, i1: 'a) : 'a susp  =
    pair (f2, f1, (f1 i1))

SML somehow "swallows" it:

- [opening /home/spela/test.sml]
val it = () : unit
opening Lazy

  datatype 'a susp = $ of 'a
val pair = fn : ('a -> 'a) * ('a -> 'a) * 'a -> 'a susp
val pair_ = fn : ('a -> 'a) * ('a -> 'a) * 'a -> 'a
val it = () : unit

Does it work? I have no idea :)

- pair ((fn x => x + 1), (fn y => y - 1), 1);
val it = $$ : int susp

I haven't read these links, but I also found an article which I also haven't read but I believe it provides answers you are looking for:

http://www.cs.mcgill.ca/~bpientka/courses/cs302-fall10/handouts/lazy-hof.pdf

I believe those links could answer your questions.

If there is anyone familiar with this topic, PLEASE, answer the question, I think it would be interesting for many of us.

Best regards, Špela